D. Driving Test

Codeforces
IDCF845D
Time2000ms
Memory256MB
Difficulty—
data structuresdpgreedy
English · Original
Chinese · Translation
Formal · Original
Polycarp has just attempted to pass the driving test. He ran over the straight road with the signs of four types. * speed limit: this sign comes with a positive integer number — maximal speed of the car after the sign (cancel the action of the previous sign of this type); * overtake is allowed: this sign means that after some car meets it, it can overtake any other car; * no speed limit: this sign cancels speed limit if any (car can move with arbitrary speed after this sign); * no overtake allowed: some car can't overtake any other car after this sign. Polycarp goes past the signs consequentially, each new sign cancels the action of all the previous signs of it's kind (speed limit/overtake). It is possible that two or more "no overtake allowed" signs go one after another with zero "overtake is allowed" signs between them. It works with "no speed limit" and "overtake is allowed" signs as well. In the beginning of the ride overtake is allowed and there is no speed limit. You are given the sequence of events in chronological order — events which happened to Polycarp during the ride. There are events of following types: 1. Polycarp changes the speed of his car to specified (this event comes with a positive integer number); 2. Polycarp's car overtakes the other car; 3. Polycarp's car goes past the "speed limit" sign (this sign comes with a positive integer); 4. Polycarp's car goes past the "overtake is allowed" sign; 5. Polycarp's car goes past the "no speed limit"; 6. Polycarp's car goes past the "no overtake allowed"; It is guaranteed that the first event in chronological order is the event of type 1 (Polycarp changed the speed of his car to specified). After the exam Polycarp can justify his rule violations by telling the driving instructor that he just didn't notice some of the signs. What is the minimal number of signs Polycarp should say he didn't notice, so that he would make no rule violations from his point of view? ## Input The first line contains one integer number _n_ (1 ≤ _n_ ≤ 2·105) — number of events. Each of the next _n_ lines starts with integer _t_ (1 ≤ _t_ ≤ 6) — the type of the event. An integer _s_ (1 ≤ _s_ ≤ 300) follows in the query of the first and the third type (if it is the query of first type, then it's new speed of Polycarp's car, if it is the query of third type, then it's new speed limit). It is guaranteed that the first event in chronological order is the event of type 1 (Polycarp changed the speed of his car to specified). ## Output Print the minimal number of road signs Polycarp should say he didn't notice, so that he would make no rule violations from his point of view. [samples] ## Note In the first example Polycarp should say he didn't notice the "speed limit" sign with the limit of 70 and the second "speed limit" sign with the limit of 120. In the second example Polycarp didn't make any rule violation. In the third example Polycarp should say he didn't notice both "no overtake allowed" that came after "overtake is allowed" sign.
Polycarp 刚刚尝试通过驾驶考试。他驶过一条笔直的道路，路上有四种类型的标志。 Polycarp 按顺序经过这些标志，每个新标志会取消之前同类型标志的作用（限速/超车）。可能存在两个或多个 "禁止超车" 标志连续出现，且它们之间没有 "允许超车" 标志；"无速度限制" 和 "允许超车" 标志也是如此。 在旅程开始时，允许超车，且无速度限制。 你将获得按时间顺序排列的事件序列——这些是 Polycarp 在驾驶过程中遇到的事件。事件类型如下： 保证按时间顺序的第一个事件是类型 #cf_span[1] 的事件（Polycarp 将他的车速调整为指定值）。 考试结束后，Polycarp 可以向驾驶教练辩解说他只是没有注意到某些标志。请问，Polycarp 最少需要声称自己没有注意到多少个标志，才能从他的视角看没有任何违规行为？ 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·10^5]）——事件的数量。 接下来的 #cf_span[n] 行，每行以一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 6]）开头，表示事件类型。 在第一类和第三类事件中，会跟随一个整数 #cf_span[s]（#cf_span[1 ≤ s ≤ 300]）；如果是第一类事件，则表示 Polycarp 的新车速；如果是第三类事件，则表示新的限速。 保证按时间顺序的第一个事件是类型 #cf_span[1] 的事件（Polycarp 将他的车速调整为指定值）。 请输出 Polycarp 最少需要声称自己没有注意到的路标数量，以便从他的视角看没有任何违规行为。 在第一个示例中，Polycarp 应声称自己没有注意到限速为 #cf_span[70] 的限速标志和第二个限速为 #cf_span[120] 的限速标志。 在第二个示例中，Polycarp 没有任何违规行为。 在第三个示例中，Polycarp 应声称自己没有注意到两个在 "允许超车" 标志之后出现的 "禁止超车" 标志。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·10^5]）——事件的数量。接下来的 #cf_span[n] 行，每行以一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 6]）开头，表示事件类型。在第一类和第三类事件中，会跟随一个整数 #cf_span[s]（#cf_span[1 ≤ s ≤ 300]）；如果是第一类事件，则表示 Polycarp 的新车速；如果是第三类事件，则表示新的限速。保证按时间顺序的第一个事件是类型 #cf_span[1] 的事件（Polycarp 将他的车速调整为指定值）。 ## Output 请输出 Polycarp 最少需要声称自己没有注意到的路标数量，以便从他的视角看没有任何违规行为。 [samples] ## Note 在第一个示例中，Polycarp 应声称自己没有注意到限速为 #cf_span[70] 的限速标志和第二个限速为 #cf_span[120] 的限速标志。在第二个示例中，Polycarp 没有任何违规行为。在第三个示例中，Polycarp 应声称自己没有注意到两个在 "允许超车" 标志之后出现的 "禁止超车" 标志。
**Definitions** Let $ n \in \mathbb{Z} $ be the number of events. Let $ E = (e_1, e_2, \dots, e_n) $ be the sequence of events, where each $ e_i $ is a tuple $ (t_i, s_i) $: - $ t_i \in \{1, 2, 3, 4, 5, 6\} $: event type - $ s_i \in \mathbb{Z} $: speed value (if $ t_i \in \{1,3\} $), otherwise undefined Event types: - $ t_i = 1 $: set speed to $ s_i $ - $ t_i = 2 $: "overtake is allowed" sign - $ t_i = 3 $: set speed limit to $ s_i $ - $ t_i = 4 $: "no overtake allowed" sign - $ t_i = 5 $: "no speed limit" sign - $ t_i = 6 $: "speed limit" sign Initial state: overtake is allowed, no speed limit. **Constraints** 1. $ 1 \le n \le 2 \cdot 10^5 $ 2. $ 1 \le t_i \le 6 $ for all $ i $ 3. $ 1 \le s_i \le 300 $ if $ t_i \in \{1,3\} $ 4. First event $ e_1 $ has $ t_1 = 1 $ **Objective** Simulate the ride with the rule: *each new sign of a type cancels the effect of all previous signs of the same type*. A violation occurs if: - Speed exceeds current speed limit (when limit is active) - Overtake is performed when "no overtake allowed" is active Polycarp can ignore (delete) any subset of signs. Find the **minimal number of signs** to delete so that **no violation occurs** during the entire sequence. Define: - Let $ S \subseteq \{1, \dots, n\} $ be the set of indices of signs to delete. - Let $ \mathcal{F} $ be the set of all feasible $ S $ such that the resulting sequence (after deleting events in $ S $) causes no violation. - Let $ T = \{ t_i \mid t_i \in \{2,3,4,5,6\} \} $ be the set of sign event types. **Minimize** $ |S| $ over all $ S \in \mathcal{F} $.
Samples
Input #1
11
1 100
3 70
4
2
3 120
5
3 120
6
1 150
4
3 300
Output #1
2
Input #2
5
1 100
3 200
2
4
5
Output #2
0
Input #3
7
1 20
2
6
4
6
6
2
Output #3
2
API Response (JSON) 
{
  "problem": {
    "name": "D. Driving Test",
    "description": {
      "content": "Polycarp has just attempted to pass the driving test. He ran over the straight road with the signs of four types. *   speed limit: this sign comes with a positive integer number — maximal speed of th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF845D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp has just attempted to pass the driving test. He ran over the straight road with the signs of four types.\n\n*   speed limit: this sign comes with a positive integer number — maximal speed of th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 刚刚尝试通过驾驶考试。他驶过一条笔直的道路，路上有四种类型的标志。\n\nPolycarp 按顺序经过这些标志，每个新标志会取消之前同类型标志的作用（限速/超车）。可能存在两个或多个 \"禁止超车\" 标志连续出现，且它们之间没有 \"允许超车\" 标志；\"无速度限制\" 和 \"允许超车\" 标志也是如此。\n\n在旅程开始时，允许超车，且无速度限制。\n\n你将获得按时间顺序排列的事件序列——这些是 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of events.  \nLet $ E = (e_1, e_2, \\dots, e_n) $ be the sequence of events, where each $ e_i $ is a tuple $ (t_i, s_i) $:  \n- $ t_i \\in \\{1, 2, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac