M. Notifications

Codeforces

IDCF10256M

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Vasya is sitting at a computer. Sometimes he receives notifications about new videos on his favourite Youtube channel. Then, You are given $n$ parameters of the notifications: the $i$-th notification is received at the moment of time $t_i$ and contains the video of length $d_i$. Find when Vasya will stop watching the last video. The first line contains the integer $n$ ($1 <= n <= 200000$) — the number of notifications. Each of the next $n$ lines contains two integers $t_i$ and $d_i$ ($1 <= t_i, d_i <= 10^9$) — the moment of time when Vasya receives the $i$-th notification, and the length of the video in this notification. All $t_i$ form non-decreasing sequence, i. e. $t_i <= t_{i + 1}$ for all $i$ from 1 to $(n -1)$. Output one integer — the moment of time when Vasya will stop watching the last video. In the given example the sequence of Vasya's actions is the following: 1) At the moment 1 he receives a notification about the video of length 4. As he isn't watching any video at the moment, he starts to watch it till the moment of time 5. 2) At the moment 3 he receives a notification about the video of length 3, but he is watching the first video at the moment, so he will start watching this video at the moment 5 (just after the first one) and finish at the moment 8. 3) At the moment 6 he receives a notification about the video of length 1. He will watch it from the moment 8 to the moment 9. 4) From the moment 9 to the moment 10, Vasya is not doing anything. 5) At the moment 10 he receives two notification — about the videos of lengths 2 and 3. He will watch them in the order he receives them, so he will watch the first of them from 10 to 12, and the other one — from 12 to 15. ## Input The first line contains the integer $n$ ($1 <= n <= 200000$) — the number of notifications.Each of the next $n$ lines contains two integers $t_i$ and $d_i$ ($1 <= t_i, d_i <= 10^9$) — the moment of time when Vasya receives the $i$-th notification, and the length of the video in this notification.All $t_i$ form non-decreasing sequence, i. e. $t_i <= t_{i + 1}$ for all $i$ from 1 to $(n -1)$. ## Output Output one integer — the moment of time when Vasya will stop watching the last video. [samples] ## Note In the given example the sequence of Vasya's actions is the following:1) At the moment 1 he receives a notification about the video of length 4. As he isn't watching any video at the moment, he starts to watch it till the moment of time 5.2) At the moment 3 he receives a notification about the video of length 3, but he is watching the first video at the moment, so he will start watching this video at the moment 5 (just after the first one) and finish at the moment 8.3) At the moment 6 he receives a notification about the video of length 1. He will watch it from the moment 8 to the moment 9.4) From the moment 9 to the moment 10, Vasya is not doing anything.5) At the moment 10 he receives two notification — about the videos of lengths 2 and 3. He will watch them in the order he receives them, so he will watch the first of them from 10 to 12, and the other one — from 12 to 15.

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of notifications. For each $ i \in \{1, \dots, n\} $, let $ t_i \in \mathbb{Z}^+ $ be the arrival time and $ d_i \in \mathbb{Z}^+ $ be the duration of the $ i $-th video notification. The sequence $ \{t_i\} $ is non-decreasing: $ t_i \leq t_{i+1} $ for all $ i \in \{1, \dots, n-1\} $. **Constraints** 1. $ 1 \leq n \leq 200000 $ 2. $ 1 \leq t_i, d_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 3. $ t_i \leq t_{i+1} $ for all $ i \in \{1, \dots, n-1\} $ **Objective** Compute the finish time $ F_n $ of the last video, where the watching schedule is determined greedily: - Let $ F_0 = 0 $. - For each $ i \in \{1, \dots, n\} $: $$ F_i = \max(F_{i-1}, t_i) + d_i $$ Output $ F_n $.

API Response (JSON)

{
  "problem": {
    "name": "M. Notifications",
    "description": {
      "content": "Vasya is sitting at a computer. Sometimes he receives notifications about new videos on his favourite Youtube channel. Then, You are given $n$ parameters of the notifications: the $i$-th notification",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10256M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vasya is sitting at a computer. Sometimes he receives notifications about new videos on his favourite Youtube channel. Then,\n\nYou are given $n$ parameters of the notifications: the $i$-th notification...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of notifications.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ t_i \\in \\mathbb{Z}^+ $ be the arrival time and $ d_i \\in \\mathbb{Z}^+ $ be the ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments