{"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":"b7fbc298-f520-5124-8934-902def70c04a","task_key":"ICPC~2dWorld~2dFinals--examples--2014~5fK","task_revision_id":"3","upstream_id":"2014_K","short_description":"Surveillance","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"# Problem Description\\n\\nThe International Corporation for Protection and Control (ICPC) develops efficient technology for protection and control. Naturally, they are keen to have their own headquarters protected and controlled. Viewed from above, the headquarters building has the shape of a convex polygon. There are several suitable places around it where cameras can be installed to monitor the building. Each camera covers a certain range of the polygon sides (building walls), depending on its position. ICPC wants to minimize the number of cameras needed to cover the whole building.\\n\\n## Input\\n\\nThe input consists of a single test case. Its first line contains two integers \\\\( n \\\\) and \\\\( k \\\\) (\\\\(3 \\\\leq n \\\\leq 10^6\\\\) and \\\\(1 \\\\leq k \\\\leq 10^6\\\\)), where \\\\( n \\\\) is the number of walls and \\\\( k \\\\) is the number of possible places for installing cameras. Each of the remaining \\\\( k \\\\) lines contains two integers \\\\( a_i \\\\) and \\\\( b_i \\\\) (\\\\(1 \\\\leq a_i, b_i \\\\leq n\\\\)). These integers specify which walls a camera at the \\\\( i \\\\)-th place would cover. If \\\\( a_i \\\\leq b_i \\\\) then the camera covers each wall \\\\( j \\\\) such that \\\\( a_i \\\\leq j \\\\leq b_i \\\\). If \\\\( a_i > b_i \\\\) then the camera covers each wall \\\\( j \\\\) such that \\\\( a_i \\\\leq j \\\\leq n \\\\) or \\\\( 1 \\\\leq j \\\\leq b_i \\\\).\\n\\n## Output\\n\\nDisplay the minimal number of cameras that suffice to cover each wall of the building. The ranges covered by two cameras may overlap. If the building cannot be covered, display `impossible` instead.\\n\\n## Sample Input and Output\\n\\n### Sample Input 1\\n```\\n100 7\\n1 50\\n50 70\\n70 90\\n90 40\\n20 60\\n60 80\\n80 20\\n```\\n\\n### Sample Output 1\\n```\\n3\\n```\\n\\n### Sample Input 2\\n```\\n8 2\\n8 3\\n5 7\\n```\\n\\n### Sample Output 2\\n```\\nimpossible\\n```\\n\\n### Sample Input 3\\n```\\n8 2\\n8 4\\n5 7\\n```\\n\\n### Sample Output 3\\n```\\n2\\n```\",\"question_title\":\"Surveillance\"}","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":[]}