H. "North-East"

Codeforces

IDCF10124H

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The popular music band of international fame "North-East" is coming to Berland! This news has spread all over the country, so numerous fans are now ready to rush and buy all the tickets! At present the fans still don't know in which cities the band plans to give concerts. The only thing is known at the moment is that the band will visit several cities, and as their name says, they will strictly move north and east when going to the next city. In other words when the band moves from city i to city j, city j is always located northward and eastward of the city i. It's also known that the tour is planned in such a way that the maximum possible number of cities will be visited. The musicians refuse to reveal other details. As you know, fans always get ready for the arrival of their idols, so they would appreciate any single detail about possible movements of their favorite musicians. Your task is to help the fans and find two lists of cities — A and B. The first list A should contain the cities, which the band might visit during the tour. The second list B should contain the cities, which the band will have to visit for sure during the tour. The first line of input contains a single integer n (1 ≤ n ≤ 105) — amount of cities in the country. The following n lines contain coordinates of the cities. Each line contains a pair of integers xi, yi ( - 106 ≤ xi, yi ≤ 106) — the coordinates of the i-th city. Ox axis is directed west-to-east, and Oy axis — south-to-north. No two given cities will be located at the same point. Print the required list A to the first line of output and B to the second line. Each list should start with the amount of cities in it, followed by the indices of cities in increasing order. Cities are numbered from 1 to n. ## Input The first line of input contains a single integer n (1 ≤ n ≤ 105) — amount of cities in the country. The following n lines contain coordinates of the cities. Each line contains a pair of integers xi, yi ( - 106 ≤ xi, yi ≤ 106) — the coordinates of the i-th city. Ox axis is directed west-to-east, and Oy axis — south-to-north. No two given cities will be located at the same point. ## Output Print the required list A to the first line of output and B to the second line. Each list should start with the amount of cities in it, followed by the indices of cities in increasing order. Cities are numbered from 1 to n. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of cities. Let $ C = \{(x_i, y_i) \mid i \in \{1, \dots, n\}\} $ be the set of city coordinates, with city $ i $ at $ (x_i, y_i) $. A city $ j $ is *northeast* of city $ i $ if $ x_j > x_i $ and $ y_j > y_i $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ -10^6 \leq x_i, y_i \leq 10^6 $ for all $ i $ 3. All points are distinct. **Objective** Find two subsets of city indices: - $ A $: the set of cities that lie on *some* longest strictly northeast path (i.e., a chain where each city is northeast of the previous). - $ B $: the set of cities that lie on *every* longest strictly northeast path. Output $ |A| $ followed by sorted indices in $ A $, then $ |B| $ followed by sorted indices in $ B $.

API Response (JSON)

{
  "problem": {
    "name": "H. \"North-East\"",
    "description": {
      "content": "The popular music band of international fame \"North-East\" is coming to Berland! This news has spread all over the country, so numerous fans are now ready to rush and buy all the tickets! At present t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10124H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The popular music band of international fame \"North-East\" is coming to Berland! This news has spread all over the country, so numerous fans are now ready to rush and buy all the tickets!\n\nAt present t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of cities.  \nLet $ C = \\{(x_i, y_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of city coordinates, with city $ i $ at $ (x_i, y_i) $.  \nA cit...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments