1429 . 彈珠臺

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

暴力又被TLE
PY派對

User's AC Ratio

57.1% (4/7)

Submission's AC Ratio

43.1% (28/65)

Tags

ioicamp ioicamp-2026

Description

彈珠臺有 $n$ 個供彈珠掉落的直軌道，編號從左到右依序為 $1$ 到 $n$。

從上到下有 $m$ 個擋板，第 $i$ 個擋板的作用是，把掉到 $[l_i, r_i]$ 這些軌道的彈珠都送到 $l_i$ 或是 $r_i$。擋板的方向 $d_i=1$ 代表會送到 $l_i$，否則 $d_i=2$ 是送到 $r_i$。

請依序處理 $q$ 筆操作，每筆操作是下列兩種之一：

  • 1 i x y z 修改第 $i$ 個擋板的資訊，讓它的作用區間變成 $[x, y]$、方向變成 $z$。
  • 2 i 從第 $i$ 個軌道最上面放一顆彈珠。

請對所有第二種操作，輸出該次放的彈珠經過所有擋板後，會落在第幾個軌道。

Input Format

輸入的第一行是三個正整數 $n, m, q$。接下來有 $m$ 行，其中的第 $i$ 行有三個正整數 $l_i, r_i, d_i$。

  • $2 \leq n \leq 2 \cdot 10^ 5$
  • $1 \leq m, q \leq 10^ 5$
  • $1 \leq l_i < r_i \leq n$
  • $1 \leq d_i \leq 2$

最後有 $q$ 行，其中的第 $i$ 行是第 $i$ 筆操作。對於第一種操作 1 i x y z 有

  • $1 \leq i \leq m$
  • $1 \leq x < y \leq n$
  • $1 \leq z \leq 2$

對於第二種操作 2 i 有

  • $1 \leq i \leq n$

所有輸入的值都是整數。保證至少有一次第二種操作。

Output Format

請對每次第二種操作，輸出一行一個整數，代表該次放的彈珠經過所有擋板後，會落在第幾個軌道。

Sample Input 1

10 5 7
7 10 1
2 4 2
3 5 1
2 6 2
9 10 1
2 1
2 2
2 9
1 5 5 9 2
2 1
2 2
2 9

Sample Output 1

1
6
7
1
9
9

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1~25 只有第二種操作 15
3 0, 26~52 $n, m, q \leq 500$ 10
4 0, 26~78 $n \leq 500$ 35
5 0~109 無額外限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 262144 65536 1 3 4 5
1 5000 262144 65536 2 5
2 5000 262144 65536 2 5
3 5000 262144 65536 2 5
4 5000 262144 65536 2 5
5 5000 262144 65536 2 5
6 5000 262144 65536 2 5
7 5000 262144 65536 2 5
8 5000 262144 65536 2 5
9 5000 262144 65536 2 5
10 5000 262144 65536 2 5
11 5000 262144 65536 2 5
12 5000 262144 65536 2 5
13 5000 262144 65536 2 5
14 5000 262144 65536 2 5
15 5000 262144 65536 2 5
16 5000 262144 65536 2 5
17 5000 262144 65536 2 5
18 5000 262144 65536 2 5
19 5000 262144 65536 2 5
20 5000 262144 65536 2 5
21 5000 262144 65536 2 5
22 5000 262144 65536 2 5
23 5000 262144 65536 2 5
24 5000 262144 65536 2 5
25 5000 262144 65536 2 5
26 5000 262144 65536 3 4 5
27 5000 262144 65536 3 4 5
28 5000 262144 65536 3 4 5
29 5000 262144 65536 3 4 5
30 5000 262144 65536 3 4 5
31 5000 262144 65536 3 4 5
32 5000 262144 65536 3 4 5
33 5000 262144 65536 3 4 5
34 5000 262144 65536 3 4 5
35 5000 262144 65536 3 4 5
36 5000 262144 65536 3 4 5
37 5000 262144 65536 3 4 5
38 5000 262144 65536 3 4 5
39 5000 262144 65536 3 4 5
40 5000 262144 65536 3 4 5
41 5000 262144 65536 3 4 5
42 5000 262144 65536 3 4 5
43 5000 262144 65536 3 4 5
44 5000 262144 65536 3 4 5
45 5000 262144 65536 3 4 5
46 5000 262144 65536 3 4 5
47 5000 262144 65536 3 4 5
48 5000 262144 65536 3 4 5
49 5000 262144 65536 3 4 5
50 5000 262144 65536 3 4 5
51 5000 262144 65536 3 4 5
52 5000 262144 65536 3 4 5
53 5000 262144 65536 4 5
54 5000 262144 65536 4 5
55 5000 262144 65536 4 5
56 5000 262144 65536 4 5
57 5000 262144 65536 4 5
58 5000 262144 65536 4 5
59 5000 262144 65536 4 5
60 5000 262144 65536 4 5
61 5000 262144 65536 4 5
62 5000 262144 65536 4 5
63 5000 262144 65536 4 5
64 5000 262144 65536 4 5
65 5000 262144 65536 4 5
66 5000 262144 65536 4 5
67 5000 262144 65536 4 5
68 5000 262144 65536 4 5
69 5000 262144 65536 4 5
70 5000 262144 65536 4 5
71 5000 262144 65536 4 5
72 5000 262144 65536 4 5
73 5000 262144 65536 4 5
74 5000 262144 65536 4 5
75 5000 262144 65536 4 5
76 5000 262144 65536 4 5
77 5000 262144 65536 4 5
78 5000 262144 65536 4 5
79 5000 262144 65536 5
80 5000 262144 65536 5
81 5000 262144 65536 5
82 5000 262144 65536 5
83 5000 262144 65536 5
84 5000 262144 65536 5
85 5000 262144 65536 5
86 5000 262144 65536 5
87 5000 262144 65536 5
88 5000 262144 65536 5
89 5000 262144 65536 5
90 5000 262144 65536 5
91 5000 262144 65536 5
92 5000 262144 65536 5
93 5000 262144 65536 5
94 5000 262144 65536 5
95 5000 262144 65536 5
96 5000 262144 65536 5
97 5000 262144 65536 5
98 5000 262144 65536 5
99 5000 262144 65536 5
100 5000 262144 65536 5
101 5000 262144 65536 5
102 5000 262144 65536 5
103 5000 262144 65536 5
104 5000 262144 65536 5
105 5000 262144 65536 5
106 5000 262144 65536 5
107 5000 262144 65536 5
108 5000 262144 65536 5
109 5000 262144 65536 5
Submit
Back to Top