QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#217181 | #5113. Bridge | ucup-team1001 | TL | 134ms | 515880kb | C++20 | 1.5kb | 2023-10-16 16:20:17 | 2023-10-16 16:20:18 |
Judging History
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...