H. Pavel's Party

Codeforces

IDCF10097H

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Pavel is going to have a party, and he wants to invite exactly k people. Pavel has n friends and he has already decided in what order he is going to call and invite them. When Pavel calls the i-th friend, he tells he will come if from ai to bi people come to the party. Once the required number of people is assembled, Pavel invites them and the party is arranged. Pavel won't call the rest friends. For every k = 1, ..., n find the number of people whom Pavel will call. The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of Pavel's friends. Each of the next n lines contains two integers ai and bi (1 ≤ ai ≤ bi ≤ n) — the lower and the upper bound of the invited people required for the i-th Pavel's friend to come. The data is listed in the order Pavel will get to know it. Output n space-separated integers. The k-th number should be equal to the number of friends called by Pavel if he wants to invite exactly k people to the party. If for some k the party cannot be arranged, output - 1 for this k. ## Input The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of Pavel's friends.Each of the next n lines contains two integers ai and bi (1 ≤ ai ≤ bi ≤ n) — the lower and the upper bound of the invited people required for the i-th Pavel's friend to come.The data is listed in the order Pavel will get to know it. ## Output Output n space-separated integers. The k-th number should be equal to the number of friends called by Pavel if he wants to invite exactly k people to the party. If for some k the party cannot be arranged, output - 1 for this k. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of friends. For each $ i \in \{1, \dots, n\} $, let $ [a_i, b_i] \subseteq \mathbb{Z}^+ $ be the interval such that friend $ i $ will attend if the total number of attendees is in $ [a_i, b_i] $. **Constraints** 1. $ 1 \leq n \leq 200000 $ 2. For all $ i \in \{1, \dots, n\} $, $ 1 \leq a_i \leq b_i \leq n $ **Objective** For each $ k \in \{1, \dots, n\} $, compute the smallest index $ p \in \{1, \dots, n\} $ such that exactly $ k $ friends among the first $ p $ satisfy $ a_i \leq k \leq b_i $, and no friend beyond $ p $ is called. If no such $ p $ exists, output $ -1 $. Formally, for each $ k \in \{1, \dots, n\} $: $$ \text{answer}[k] = \min \left\{ p \in \{1, \dots, n\} \ \middle| \ \left| \left\{ i \in \{1, \dots, p\} \mid a_i \leq k \leq b_i \right\} \right| = k \right\} $$ If the set is empty, $ \text{answer}[k] = -1 $.

API Response (JSON)

{
  "problem": {
    "name": "H. Pavel's Party",
    "description": {
      "content": "Pavel is going to have a party, and he wants to invite exactly k people. Pavel has n friends and he has already decided in what order he is going to call and invite them. When Pavel calls the i-th fr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10097H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Pavel is going to have a party, and he wants to invite exactly k people.\n\nPavel has n friends and he has already decided in what order he is going to call and invite them. When Pavel calls the i-th fr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of friends.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ [a_i, b_i] \\subseteq \\mathbb{Z}^+ $ be the interval such that friend $ i $ will atten...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments