{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"hlce","formal_name":"Humanity's Last Code Exam","introduction":"Humanity's Last Code Exam evaluates problem solving and code generation using ICPC World Finals and IOI problems. The project describes 235 problems; this import selects its public ICPC dataset of 146 problems.","introduction_ja":"","introduction_en":"","category":"Category not supplied","task_count":null,"acquisition_status":"Acquisition status not supplied","official_url":"https://humanity-s-last-code-exam.github.io/website/","indexing_mode":"noindex","profile":{"resources":[],"task_format":"","scoring":"","metric":"","size":"","answer_access":"","license":"","citation":"","maintainer":"","released":"","why_hard":"","related":[]}},"task_id":"3fca97e7-8631-5d3f-8748-a4754f32b4d5","task_key":"ICPC~2dWorld~2dFinals--examples--2019~5fF","task_revision_id":"2","upstream_id":"2019_F","short_description":"Directing Rainfall","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem Statement\\n\\nPorto and the nearby Douro Valley are famous for producing port wine. Wine lovers from all over the world come here to enjoy this sweet wine where it is made. The International Consortium of Port Connoisseurs (ICPC) is organizing tours to the vineyards that are upstream on the Douro River. To make visits more pleasurable for tourists, the ICPC has recently installed sun tarps above the vineyards. The tarps protect tourists from sunburn when strolling among the vines and sipping on a vintage port.\\n\\nUnfortunately, there is a small problem with the tarps. Grapes need sunlight and water to grow. While the tarps let through enough sunlight, they are entirely waterproof. This means that rainwater might not reach the vineyards below. If nothing is done, this year’s wine harvest is in peril!\\n\\nThe ICPC wants to solve their problem by puncturing the tarps so that they let rainwater through to the vineyards below. Since there is little time to waste before the rainy season starts, the ICPC wants to make the minimum number of punctures that achieve this goal.\\n\\nWe will consider a two-dimensional version of this problem. The vineyard to be watered is an interval on the x-axis, and the tarps are modeled as line segments above the x-axis. The tarps are slanted, that is, not parallel to the x- or y-axes. Rain falls straight down from infinitely high. When any rain falls on a tarp, it flows toward the tarp’s lower end and falls off from there, unless there is a puncture between the place where the rain falls and the tarp’s lower end—in which case the rain will fall through the puncture instead. After the rain falls off a tarp, it continues to fall vertically. This repeats until the rain hits the ground (the x-axis).\\n\\nFor legal reasons, you have to ensure that at least some of the rain that reaches the vineyard originated from directly above the vineyard. This is to prevent any vineyard from stealing all their rain from neighboring vineyards.\\n\\n### Input\\n\\nThe first line of input contains three integers `l`, `r`, and `n`, where \\\\((l, r)\\\\) \\\\((0 \\\\leq l < r \\\\leq 10^9)\\\\) is the interval representing the vineyard and \\\\(n\\\\) \\\\((0 \\\\leq n \\\\leq 5 \\\\times 10^5)\\\\) is the number of tarps. Each of the following \\\\(n\\\\) lines describes a tarp and contains four integers \\\\(x_1, y_1, x_2, y_2\\\\), where \\\\((x_1, y_1)\\\\) is the position of the tarp’s lower end and \\\\((x_2, y_2)\\\\) is the position of the higher end \\\\((0 \\\\leq x_1, x_2 \\\\leq 10^9, x_1 \\\\neq x_2, \\\\text{and } 0 < y_1 < y_2 \\\\leq 10^9)\\\\).\\n\\nThe x-coordinates given in the input \\\\((l, r, \\\\text{and the values of } x_1 \\\\text{ and } x_2 \\\\text{ for all tarps})\\\\) are all distinct. The tarps described in the input will not intersect, and no endpoint of a tarp will lie on another tarp.\\n\\n### Output\\n\\nOutput the smallest number of punctures that need to be made to get some rain falling from above the vineyard to the vineyard.\\n\\n### Sample Input 1\\n\\n```\\n10 20 5\\n32 50 12 60\\n30 60 8 70\\n25 70 0 80\\n15 30 28 40\\n5 20 14 25\\n```\\n\\n### Sample Output 1\\n\\n```\\n2\\n```\\n\\n### Sample Input 2\\n\\n```\\n2 4 2\\n3 2 0 3\\n5 2 1 5\\n```\\n\\n### Sample Output 2\\n\\n```\\n1\\n```\",\"question_title\":\"Directing Rainfall\"}","display_format":"text","language":"","answer_status":"published","assets":[],"source_url":"https://humanity-s-last-code-exam.github.io/website/","history":"initial import","indexing_mode":"noindex","subproblems":[],"grids":[]}