QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#217181#5113. Bridgeucup-team1001TL 134ms515880kbC++201.5kb2023-10-16 16:20:172023-10-16 16:20:18

Judging History

你现在查看的是最新测评结果

  • [2023-10-16 16:20:18]
  • 评测
  • 测评结果:TL
  • 用时:134ms
  • 内存:515880kb
  • [2023-10-16 16:20:17]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;

#define irep(i,l,r) for(int i = l; i <= r; ++ i)

const int N = 100099;
const int len = 420;
const int K = N / len + 50;
int per[N][655],invp[N][655];
stack<array<int, 2>>p[655];
// clo, line
inline int read(){
	char ch = getchar();
	int s = 0;
	while(!isdigit(ch))ch = getchar();
	while(isdigit(ch))s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
	return s;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n = read(), m = read(), q = read();
	
	for(int c = 0; c <= m / len; c ++){
		for(int i = 1; i <= n; ++ i){
			per[i][c] = invp[i][c] = i;
		}
	}
	while(q --){
		int op = read();
		if(op == 1){
			int line = read(), cloumn = read();
			int x = cloumn / len;
			array<int, 2> PI = {cloumn, line};
			stack<array<int, 2>>temp;
			
			while(p[x].size()){
				auto [c, l] = p[x].top();
				if(c < cloumn)break;
				temp.push(p[x].top());
				per[invp[l][x]][x] = l + 1;
				per[invp[l + 1][x]][x] = l;
				swap(invp[l][x], invp[l + 1][x]);
				p[x].pop();
			}
			temp.push(PI);
			
			while(temp.size()){
				auto [c, l] = temp.top();
				per[invp[l][x]][x] = l + 1;
				per[invp[l + 1][x]][x] = l;
				swap(invp[l][x], invp[l + 1][x]);
				p[x].push(temp.top());
				temp.pop();
			}
		}
		else{
			int a = read();
			for(int x = 0; x <= m / len; ++ x){
				a = per[a][x];
			}
			cout << a << '\n';
		}
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5980kb

input:

3 4 13
2 2
1 1 3
2 1
2 2
2 3
1 2 4
2 1
2 2
2 3
1 2 1
2 1
2 2
2 3

output:

2
2
1
3
3
1
2
3
2
1

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 59ms
memory: 6140kb

input:

3 100000 99997
2 2
2 2
2 3
2 3
2 3
2 3
2 3
1 2 11047
1 1 98732
1 2 90045
1 1 43556
2 1
2 3
1 2 17242
1 1 17027
2 1
1 1 94195
2 1
2 2
2 1
2 3
1 1 34124
1 2 14354
1 2 673
1 2 39812
1 2 35520
1 2 16046
2 3
2 2
1 1 25410
2 3
2 1
2 3
2 2
1 2 55684
2 1
1 2 24811
1 2 92268
1 2 60268
2 2
1 1 89272
1 2 19232...

output:

2
2
3
3
3
3
3
3
2
1
2
1
2
3
3
1
1
2
1
3
3
2
1
3
2
1
2
1
2
2
2
2
1
1
2
1
3
2
1
3
2
1
3
2
2
1
3
3
2
3
2
3
1
2
1
1
2
3
2
1
3
2
3
2
3
2
2
1
1
2
1
1
2
3
2
1
1
3
1
1
2
2
3
2
2
1
1
1
2
3
3
1
1
2
1
1
3
1
3
2
3
2
3
2
2
2
3
3
2
2
2
3
3
2
2
2
3
1
2
1
1
3
2
3
2
2
2
1
1
1
3
3
3
2
1
1
3
3
3
1
1
2
3
2
3
3
3
3
2
3
...

result:

ok 60761 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 515880kb

input:

100000 5 20
1 40277 1
2 55431
2 22404
2 29137
2 10206
2 72758
2 92880
1 96104 2
2 12641
1 99618 2
2 88481
1 76531 3
1 91957 5
1 23999 2
2 35922
1 69730 5
1 16353 2
1 90312 1
1 75264 5
2 77283

output:

55431
22404
29137
10206
72758
92880
12641
88481
35922
77283

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 5968kb

input:

3 5 20
2 3
1 2 2
2 3
1 1 4
2 1
1 2 5
1 1 1
2 1
2 2
2 1
2 1
2 2
2 3
2 3
2 1
2 1
2 1
2 3
2 2
2 3

output:

3
2
2
2
3
2
2
3
1
1
2
2
2
1
3
1

result:

ok 16 numbers

Test #5:

score: 0
Accepted
time: 72ms
memory: 8688kb

input:

200 100000 99995
1 180 45150
2 137
1 97 78979
1 14 74747
1 151 41036
1 178 88736
1 26 50618
1 132 72623
1 95 37475
2 184
1 31 44675
1 183 14874
1 66 14597
2 191
2 102
1 27 61558
1 36 39304
2 119
2 185
1 156 50000
2 200
2 152
1 17 51778
1 39 39403
2 168
1 50 67213
1 92 56771
2 28
2 196
1 99 29006
2 4...

output:

137
184
191
102
119
185
200
151
168
27
196
43
73
16
28
64
88
106
139
117
90
131
64
64
107
11
38
149
133
184
166
20
95
185
71
85
151
96
106
103
91
45
195
112
82
113
183
178
47
112
12
185
41
153
77
179
44
165
84
111
192
161
144
33
139
9
37
38
177
45
146
83
88
166
1
180
175
180
12
166
186
44
2
115
124
...

result:

ok 50281 numbers

Test #6:

score: 0
Accepted
time: 134ms
memory: 10320kb

input:

200 100 100000
1 192 88
1 13 2
2 131
1 80 44
1 11 74
1 159 89
1 29 91
1 81 62
1 159 21
1 37 34
2 169
2 163
1 164 50
1 104 45
1 81 46
1 176 73
1 68 59
2 117
2 152
2 189
1 125 4
2 45
1 120 59
2 30
2 113
1 74 15
1 147 71
1 31 47
2 179
2 118
2 34
2 61
1 41 32
2 153
1 186 28
2 113
2 55
2 24
2 92
2 72
2 8...

output:

131
169
163
117
152
189
45
29
113
179
118
34
61
153
113
55
24
92
72
8
152
85
174
188
18
158
152
164
101
156
79
81
146
15
94
90
23
81
200
153
181
181
135
31
145
44
88
143
11
134
25
80
183
79
187
29
92
195
123
76
14
135
28
193
116
33
179
76
45
169
91
85
141
138
166
195
53
117
127
86
84
101
132
115
1
9...

result:

ok 91618 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 5940kb

input:

10 100 20
1 7 12
1 7 48
2 7
1 4 92
2 4
2 7
2 6
1 8 23
2 1
1 8 83
2 3
1 8 33
1 9 72
2 1
2 8
1 9 4
1 6 6
2 1
2 1
2 10

output:

7
5
7
6
1
3
1
9
1
1
10

result:

ok 11 numbers

Test #8:

score: 0
Accepted
time: 68ms
memory: 8748kb

input:

200 100000 99995
1 1 29447
2 147
2 132
2 90
1 140 58754
2 74
2 51
2 113
1 177 51453
1 160 35609
2 47
1 88 93756
2 17
2 180
1 9 95689
2 196
1 59 45390
2 90
1 156 83976
2 17
1 66 13781
1 68 82550
2 174
2 14
1 24 41452
1 29 39524
2 2
1 190 55163
1 27 80396
1 102 20535
2 112
2 66
1 69 84633
1 95 51235
1...

output:

147
132
90
74
51
113
47
17
180
196
90
17
174
14
1
112
67
73
58
93
61
41
54
90
9
14
28
61
42
118
15
137
119
127
162
118
100
83
177
171
159
30
24
23
183
120
90
104
102
70
70
62
88
111
149
37
168
75
54
175
132
164
89
114
69
132
184
81
62
38
197
101
24
115
187
16
153
170
29
142
191
134
165
41
168
171
11...

result:

ok 50221 numbers

Test #9:

score: 0
Accepted
time: 3ms
memory: 6036kb

input:

3 100 99997
1 1 47
2 2
2 1
1 1 46
1 1 9
2 1
1 1 98
2 1
1 2 93
1 2 71
1 2 67
2 2
1 1 43
2 1
2 2
2 2
1 1 85
1 2 86
1 2 97
1 1 84
2 3
2 1
2 3
1 1 23
2 3
1 1 13
1 2 34
2 3
2 3
2 3
1 2 94
2 1
1 2 31
2 3
2 1
2 2
2 3
2 3
2 3
1 1 83
2 1
2 3
1 2 77
2 3
2 1
2 3
1 2 89
2 3
2 3
1 1 74
2 3
2 2
2 2
2 1
1 1 78
2 1...

output:

1
2
2
1
2
2
3
3
1
2
1
1
2
2
2
3
3
2
1
3
3
3
1
3
2
1
2
2
2
2
3
3
1
1
1
1
1
2
3
3
2
3
1
3
1
1
2
2
3
2
3
3
1
2
2
1
3
3
2
3
2
1
3
3
1
3
3
3
3
1
2
3
2
3
1
3
1
1
3
3
1
2
1
1
3
3
2
1
2
3
2
1
1
1
2
1
3
2
3
1
2
2
3
2
3
1
2
1
1
3
2
1
1
3
3
1
2
3
2
1
3
3
2
1
3
3
1
2
3
3
2
1
3
1
2
2
3
2
1
2
2
3
3
3
2
2
3
3
2
2
...

result:

ok 99897 numbers

Test #10:

score: 0
Accepted
time: 6ms
memory: 5996kb

input:

10 100 99996
2 2
2 1
2 5
1 8 23
1 5 44
1 6 86
1 3 38
1 5 65
1 8 87
1 6 9
1 6 62
2 4
2 10
2 6
2 2
1 4 14
1 4 54
1 2 7
2 9
1 1 41
2 8
1 1 52
2 8
1 6 63
2 3
1 2 27
2 1
1 6 99
2 5
1 8 16
1 1 16
1 4 35
2 1
2 4
1 4 25
2 2
1 2 66
2 10
1 7 56
2 5
1 2 70
1 8 32
2 2
1 6 71
2 9
1 6 33
1 8 74
1 6 31
1 7 24
2 10...

output:

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

result:

ok 99577 numbers

Test #11:

score: 0
Accepted
time: 3ms
memory: 5932kb

input:

10 100 100000
2 6
2 4
2 8
1 5 70
2 4
1 3 55
1 7 89
1 1 57
1 9 40
1 3 83
2 7
2 9
1 5 26
2 7
1 1 99
2 8
1 1 13
2 8
1 3 86
1 6 12
1 5 11
1 9 98
2 2
1 1 63
1 5 67
1 5 66
1 8 58
2 4
1 9 71
1 1 71
1 5 89
1 1 17
2 3
2 10
1 2 59
2 5
2 2
2 5
1 6 8
1 1 45
1 3 69
1 5 63
2 5
1 5 35
1 2 19
1 4 8
2 1
2 1
2 10
1 2...

output:

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

result:

ok 99580 numbers

Test #12:

score: 0
Accepted
time: 1ms
memory: 5928kb

input:

10 100 20
2 9
2 7
2 4
1 2 8
2 8
1 2 1
2 9
1 3 35
1 6 37
1 9 45
1 8 20
2 10
1 6 5
2 5
1 4 91
2 1
1 6 94
1 7 60
1 8 96
1 5 1

output:

9
7
4
8
9
9
5
1

result:

ok 8 numbers

Test #13:

score: 0
Accepted
time: 0ms
memory: 10148kb

input:

200 100000 20
2 67
2 2
2 183
1 113 37023
2 191
1 138 85049
2 118
1 139 45917
2 77
2 22
1 163 58926
2 105
2 47
1 154 52742
2 193
1 7 38889
2 196
2 101
2 55
1 37 36657

output:

67
2
183
191
118
77
22
105
47
193
196
101
55

result:

ok 13 numbers

Test #14:

score: 0
Accepted
time: 59ms
memory: 6236kb

input:

3 100000 100000
1 2 27703
2 1
1 1 4733
2 3
1 1 35779
2 3
1 2 75051
1 1 55567
1 2 67461
2 2
2 3
2 2
1 2 40504
2 2
1 2 66898
2 2
2 2
2 3
2 2
1 1 49407
1 1 40531
2 2
1 1 16364
1 1 20583
2 1
1 2 15074
2 3
1 2 52463
1 2 68707
2 3
1 1 2943
1 1 49490
1 1 21186
2 2
1 2 60207
2 3
1 1 69753
2 2
1 2 55020
1 2 ...

output:

1
2
1
1
2
1
3
2
2
3
2
2
1
1
3
3
1
2
1
3
3
2
3
1
1
3
1
3
2
3
1
2
1
2
3
1
1
1
1
1
3
3
3
3
1
2
1
3
3
3
1
1
2
1
3
3
2
2
1
3
3
3
1
2
2
1
1
2
1
1
3
1
2
1
1
1
3
3
3
2
1
2
1
3
1
1
1
3
2
2
3
1
1
3
2
1
2
2
3
2
3
2
2
3
1
1
3
1
1
2
2
2
2
3
1
1
1
3
1
2
3
3
2
2
2
3
2
2
1
1
1
3
3
2
1
3
1
1
2
1
2
3
2
3
3
1
1
2
3
2
...

result:

ok 60629 numbers

Test #15:

score: 0
Accepted
time: 71ms
memory: 6888kb

input:

200 100000 99996
1 9 50789
2 13
2 119
2 140
2 17
2 152
2 55
1 13 78327
1 86 75223
1 124 45493
1 61 18265
2 27
1 83 46963
2 44
2 2
1 24 66690
1 60 83558
2 190
1 17 74439
1 46 33383
1 33 865
1 65 31179
1 126 66418
1 24 87240
1 157 70780
1 39 64647
2 74
2 112
1 34 94471
1 118 59390
2 122
2 133
2 159
1 ...

output:

13
119
140
17
152
55
27
44
2
190
74
112
122
133
159
1
21
131
102
78
42
117
153
44
56
115
111
15
22
11
30
81
162
11
26
77
190
76
103
137
2
192
107
13
176
88
75
193
59
14
41
196
23
6
114
121
150
143
172
121
119
117
130
179
131
130
138
107
181
45
22
75
6
79
175
177
44
92
167
82
155
197
119
109
167
146
...

result:

ok 50119 numbers

Test #16:

score: -100
Time Limit Exceeded

input:

100000 100 99997
2 83146
1 92304 70
2 1316
2 67332
1 3999 7
1 87638 98
2 46517
2 9036
2 72931
1 99147 75
1 81076 94
2 35556
1 38226 77
1 70606 61
1 97514 72
2 59772
1 51823 100
1 34436 19
1 2566 38
2 35420
1 52972 14
1 59064 59
1 61862 80
1 23386 91
1 20343 59
2 40701
2 64037
2 92058
2 58963
2 30254...

output:

83146
1316
67332
46517
9036
72931
35556
59772
35420
40701
64037
92058
58963
30254
960
27193
30536
34081
49930
17706
61236
23210
1769
49001
45989
2314
66544
29516
16869
48166
18813
46466
12667
2769
13587
595
30471
96700
74682
54428
24624
79741
35016
63668
97575
8010
10202
30058
62498
98512
52240
2020...

result: