QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #845151 | #4356. Giraffes | KingPowers | 100 ✓ | 1322ms | 20080kb | C++14 | 3.3kb | 2025-01-06 15:09:17 | 2025-01-06 15:09:17 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
#define lowbit(x) ((x) & (-x))
using namespace std;
using pii = pair<int, int>;
const int N = 20005, INF = 1e9;
int n, ans, a[N], b[N], f[N][4], g[N][4];
vector<pii> rec[8][N];
template<typename T> inline void cmax(T &x, T y){x = max(x, y);}
template<typename T> inline void cmin(T &x, T y){x = min(x, y);}
struct BIT1{
int t[N];
inline void clear(){fill(t + 1, t + 2 * n + 1, INF);}
inline void add(int x, int y){for(; x <= 2 * n; x += lowbit(x)) cmin(t[x], y);}
inline int query(int x){int res = INF; for(; x; x -= lowbit(x)) cmin(res, t[x]); return res;}
}t1;
struct BIT2{
int t[N];
inline void clear(){fill(t + 1, t + 2 * n + 1, INF);}
inline void add(int x, int y){for(; x; x -= lowbit(x)) cmin(t[x], y);}
inline int query(int x){int res = INF; for(; x <= 2 * n; x += lowbit(x)) cmin(res, t[x]); return res;}
}t2;
inline void addrec(int l, int r, int d){
int u = d + r - l;
rec[0][l].emplace_back(n + d - l, u); //0
rec[1][d].emplace_back(n + d - l, r);
rec[2][r].emplace_back(d + r, u); //1
rec[3][d].emplace_back(d + r, -l);
rec[4][r].emplace_back(n + d - l, -d); //2
rec[5][u].emplace_back(n + d - l, -l);
rec[6][l].emplace_back(d + r, -d); //3
rec[7][u].emplace_back(d + r, r);
}
void Solve(){
cin >> n;
For(i, 1, n) cin >> a[i], b[a[i]] = i;
ans++;
while(true){
For(i, 0, 7) For(j, 1, n) rec[i][j].clear();
For(i, 1, n) For(j, 0, 3) g[i][j] = INF;
For(i, 1, n){
if(f[i][0] <= min(n - i, n - a[i])) addrec(i, i + f[i][0], a[i]);
if(f[i][1] <= min(i - 1, n - a[i])) addrec(i - f[i][1], i, a[i]);
if(f[i][2] <= min(i - 1, a[i] - 1)) addrec(i - f[i][2], i, a[i] - f[i][2]);
if(f[i][3] <= min(n - i, a[i] - 1)) addrec(i, i + f[i][3], a[i] - f[i][3]);
}
t1.clear(); t2.clear();
Rof(i, n, 1){
cmin(g[i][0], t2.query(n + a[i] - i) - a[i]);
for(auto [j, k] : rec[0][i]) t2.add(j, k);
}
Rof(i, n, 1){
cmin(g[b[i]][0], t1.query(n + i - b[i]) - b[i]);
for(auto [j, k] : rec[1][i]) t1.add(j, k);
}
t1.clear(); t2.clear();
For(i, 1, n){
cmin(g[i][1], t2.query(i + a[i]) - a[i]);
for(auto [j, k] : rec[2][i]) t2.add(j, k);
}
Rof(i, n, 1){
cmin(g[b[i]][1], t1.query(b[i] + i) + b[i]);
for(auto [j, k] : rec[3][i]) t1.add(j, k);
}
t1.clear(); t2.clear();
For(i, 1, n){
cmin(g[i][2], t1.query(n + a[i] - i) + a[i]);
for(auto [j, k] : rec[4][i]) t1.add(j, k);
}
For(i, 1, n){
cmin(g[b[i]][2], t2.query(n + i - b[i]) + b[i]);
for(auto [j, k] : rec[5][i]) t2.add(j, k);
}
t1.clear(); t2.clear();
Rof(i, n, 1){
cmin(g[i][3], t1.query(i + a[i]) + a[i]);
for(auto [j, k] : rec[6][i]) t1.add(j, k);
}
For(i, 1, n){
cmin(g[b[i]][3], t2.query(i + b[i]) - b[i]);
for(auto [j, k] : rec[7][i]) t2.add(j, k);
}
bool flag = 0;
For(i, 1, n) For(j, 0, 3) f[i][j] = g[i][j];
For(i, 1, n){
if(f[i][0] <= min(n - i, n - a[i])) flag = 1;
if(f[i][1] <= min(i - 1, n - a[i])) flag = 1;
if(f[i][2] <= min(i - 1, a[i] - 1)) flag = 1;
if(f[i][3] <= min(n - i, a[i] - 1)) flag = 1;
}
if(!flag) break; ans++;
}
cout << n - ans << '\n';
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int T = 1; //cin >> T;
while(T--) Solve();
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 8360kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 10
Accepted
time: 2ms
memory: 7464kb
input:
2 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: 10
Accepted
time: 0ms
memory: 7792kb
input:
3 1 2 3
output:
0
result:
ok single line: '0'
Test #4:
score: 10
Accepted
time: 0ms
memory: 8604kb
input:
4 3 1 4 2
output:
2
result:
ok single line: '2'
Test #5:
score: 10
Accepted
time: 2ms
memory: 7320kb
input:
5 3 4 5 1 2
output:
2
result:
ok single line: '2'
Test #6:
score: 10
Accepted
time: 0ms
memory: 8500kb
input:
6 1 5 6 2 4 3
output:
2
result:
ok single line: '2'
Test #7:
score: 10
Accepted
time: 2ms
memory: 7320kb
input:
6 1 6 3 4 2 5
output:
0
result:
ok single line: '0'
Test #8:
score: 10
Accepted
time: 2ms
memory: 7468kb
input:
7 5 3 4 6 2 7 1
output:
0
result:
ok single line: '0'
Test #9:
score: 10
Accepted
time: 0ms
memory: 7320kb
input:
7 5 3 7 1 2 6 4
output:
3
result:
ok single line: '3'
Test #10:
score: 10
Accepted
time: 2ms
memory: 8252kb
input:
7 5 2 3 6 7 1 4
output:
2
result:
ok single line: '2'
Subtask #2:
score: 22
Accepted
Test #11:
score: 22
Accepted
time: 2ms
memory: 7844kb
input:
8 7 2 1 8 3 5 4 6
output:
3
result:
ok single line: '3'
Test #12:
score: 22
Accepted
time: 0ms
memory: 7792kb
input:
9 3 1 5 6 8 4 7 9 2
output:
3
result:
ok single line: '3'
Test #13:
score: 22
Accepted
time: 1ms
memory: 7984kb
input:
10 4 6 5 7 1 2 3 8 9 10
output:
2
result:
ok single line: '2'
Test #14:
score: 22
Accepted
time: 2ms
memory: 8380kb
input:
11 2 10 3 11 1 5 8 6 4 7 9
output:
5
result:
ok single line: '5'
Test #15:
score: 22
Accepted
time: 2ms
memory: 7936kb
input:
12 2 7 3 1 9 4 8 12 11 6 5 10
output:
5
result:
ok single line: '5'
Test #16:
score: 22
Accepted
time: 2ms
memory: 8424kb
input:
12 11 7 4 10 8 3 1 9 12 6 5 2
output:
5
result:
ok single line: '5'
Test #17:
score: 22
Accepted
time: 2ms
memory: 7844kb
input:
13 11 4 8 5 9 2 3 7 13 12 1 10 6
output:
7
result:
ok single line: '7'
Test #18:
score: 22
Accepted
time: 0ms
memory: 8532kb
input:
13 6 3 10 8 13 11 4 1 7 5 12 9 2
output:
7
result:
ok single line: '7'
Test #19:
score: 22
Accepted
time: 2ms
memory: 7936kb
input:
13 11 4 8 2 7 6 5 12 10 1 13 9 3
output:
5
result:
ok single line: '5'
Test #20:
score: 22
Accepted
time: 2ms
memory: 7804kb
input:
13 4 2 6 7 11 5 3 9 10 1 8 13 12
output:
6
result:
ok single line: '6'
Subtask #3:
score: 27
Accepted
Test #21:
score: 27
Accepted
time: 0ms
memory: 8800kb
input:
29 7 22 11 16 27 1 24 12 6 21 13 2 10 8 25 15 4 19 17 9 23 5 14 20 18 28 26 29 3
output:
17
result:
ok single line: '17'
Test #22:
score: 27
Accepted
time: 0ms
memory: 9116kb
input:
96 80 30 84 26 53 63 96 48 15 40 35 10 81 68 55 57 25 2 41 56 64 65 42 74 93 69 58 32 21 85 14 79 22 38 51 8 5 27 19 20 16 94 31 23 86 36 17 77 75 62 12 87 71 76 11 13 52 44 45 4 46 60 54 3 73 70 72 66 67 92 88 59 61 7 34 89 24 49 18 37 28 91 47 1 90 9 95 82 83 33 29 78 50 6 43 39
output:
73
result:
ok single line: '73'
Test #23:
score: 27
Accepted
time: 4ms
memory: 8032kb
input:
185 152 65 146 109 33 14 44 141 174 154 37 11 177 39 82 58 70 36 81 163 76 98 20 182 129 142 64 5 126 91 25 55 42 105 173 155 121 96 50 102 178 66 22 168 99 7 115 183 27 95 93 23 3 181 106 84 89 171 18 148 156 41 162 47 139 112 86 35 97 134 12 77 160 13 34 118 104 111 15 2 46 51 136 87 110 145 71 15...
output:
151
result:
ok single line: '151'
Test #24:
score: 27
Accepted
time: 5ms
memory: 7840kb
input:
242 3 137 21 188 170 212 192 186 122 144 165 43 27 109 156 52 108 222 98 151 155 228 183 124 7 17 26 217 68 82 229 1 169 92 47 206 29 145 149 241 185 196 99 44 67 51 139 153 141 128 73 104 142 219 119 50 36 161 178 18 11 193 54 107 70 102 49 103 20 13 78 9 59 40 63 30 31 12 159 45 234 60 69 225 242 ...
output:
202
result:
ok single line: '202'
Test #25:
score: 27
Accepted
time: 6ms
memory: 9132kb
input:
289 248 83 121 198 220 113 282 276 157 88 211 15 187 109 110 180 127 246 86 241 116 69 255 11 245 91 240 58 242 212 52 141 38 138 75 239 31 270 124 151 247 94 160 188 237 54 139 40 5 192 85 92 165 131 207 260 278 251 106 269 226 234 105 222 70 230 146 283 254 32 66 199 178 231 256 258 73 221 261 76 ...
output:
245
result:
ok single line: '245'
Test #26:
score: 27
Accepted
time: 3ms
memory: 9240kb
input:
296 103 239 226 164 159 121 290 217 29 172 288 100 138 276 104 157 73 177 93 89 238 143 32 152 273 74 189 195 155 258 44 84 43 286 36 124 201 24 116 85 35 223 123 54 291 191 46 30 55 49 171 190 106 289 206 111 196 137 40 113 219 222 98 96 97 269 194 95 94 80 224 188 283 63 51 281 70 18 136 213 125 2...
output:
255
result:
ok single line: '255'
Test #27:
score: 27
Accepted
time: 3ms
memory: 8368kb
input:
297 105 116 45 5 220 20 219 83 7 284 250 100 55 180 64 196 268 70 209 9 136 89 189 240 174 238 84 56 175 207 200 255 292 166 79 222 32 130 218 65 156 217 272 123 27 71 48 51 287 194 106 135 223 81 177 163 3 22 77 78 144 33 275 262 264 23 69 214 193 291 170 184 13 146 73 87 107 158 203 19 59 265 67 4...
output:
253
result:
ok single line: '253'
Test #28:
score: 27
Accepted
time: 6ms
memory: 9360kb
input:
298 135 130 5 295 199 1 46 102 224 226 286 93 98 188 62 197 152 298 266 176 86 53 34 20 99 219 114 207 246 32 181 158 85 274 28 18 108 257 127 249 248 134 245 143 97 52 47 178 154 282 283 174 241 123 221 87 94 186 201 182 294 191 225 19 100 194 80 37 297 254 74 104 146 261 169 177 13 272 238 211 192...
output:
256
result:
ok single line: '256'
Test #29:
score: 27
Accepted
time: 3ms
memory: 8720kb
input:
299 193 83 158 227 11 27 149 289 216 55 74 56 187 144 22 127 121 226 190 292 143 37 160 199 171 294 179 260 293 188 217 25 5 128 238 243 237 248 131 299 176 19 78 136 175 6 155 222 103 259 261 247 42 12 134 152 197 139 80 256 147 20 298 228 157 173 146 184 94 265 274 205 117 110 194 166 280 251 286 ...
output:
255
result:
ok single line: '255'
Test #30:
score: 27
Accepted
time: 6ms
memory: 8288kb
input:
300 64 132 183 256 34 160 244 53 206 216 291 81 262 122 62 94 230 107 2 39 118 213 171 178 26 4 159 9 67 130 274 95 277 221 181 249 211 108 86 210 298 299 141 90 276 272 209 93 252 275 104 191 247 219 280 23 71 220 7 70 61 300 41 142 235 133 162 212 248 251 28 147 222 145 5 227 199 173 236 50 156 11...
output:
252
result:
ok single line: '252'
Subtask #4:
score: 41
Accepted
Test #31:
score: 41
Accepted
time: 124ms
memory: 10680kb
input:
2317 1841 533 998 38 1358 1204 1174 176 581 1719 550 906 35 101 442 1068 1781 601 1368 2190 2095 919 2186 1134 1814 625 90 2007 653 186 204 997 1607 1675 45 806 483 299 27 935 1070 1425 1822 1712 2074 2259 264 840 1960 1045 1742 1185 577 142 980 151 2136 2143 955 462 1373 395 1300 185 637 734 803 13...
output:
2188
result:
ok single line: '2188'
Test #32:
score: 41
Accepted
time: 596ms
memory: 15972kb
input:
5832 1722 2970 5519 3937 611 905 5560 3982 2598 4702 1508 3021 4042 2233 2271 4583 1554 1867 1640 2659 2580 1468 413 2708 533 4008 5152 3074 2466 1521 5101 1797 5453 702 25 3750 1781 1598 1755 2091 1894 786 3591 4058 5088 5307 2926 2222 1708 256 1249 1815 5505 3273 2016 4315 1161 2376 5409 612 1157 ...
output:
5626
result:
ok single line: '5626'
Test #33:
score: 41
Accepted
time: 1249ms
memory: 18940kb
input:
7993 444 5307 3841 3057 5739 487 4824 7828 1189 692 1095 1529 2503 1401 6936 3688 5934 3393 7793 1068 4160 1109 4933 3844 3137 6057 4296 825 5432 2159 3365 1819 7530 4753 463 6298 1029 5558 3398 5323 1448 2120 23 913 2592 3758 2740 5811 5295 7460 3068 37 3075 5838 7248 7348 2019 5679 7261 5176 5235 ...
output:
7748
result:
ok single line: '7748'
Test #34:
score: 41
Accepted
time: 1322ms
memory: 19408kb
input:
7994 3179 1801 4177 2524 5297 7481 3410 4287 7420 7465 6657 7229 5939 2570 3316 286 1989 7006 2015 6818 7717 4004 1929 2486 2201 4352 791 714 3435 5766 773 1836 7130 7662 5885 6424 7538 2098 471 1563 677 2738 1525 728 5740 3412 5416 4808 2773 2449 1765 41 6811 1990 2511 4540 4908 2971 3361 6863 3466...
output:
7753
result:
ok single line: '7753'
Test #35:
score: 41
Accepted
time: 1225ms
memory: 19528kb
input:
7995 298 3649 6679 293 2589 5476 6327 7299 5804 5311 4672 1238 3698 5027 4219 3496 5409 2987 1466 5799 2031 7653 1172 7424 3645 5625 6568 2157 3030 5177 1492 7478 6644 4286 1612 59 6805 3222 6703 4742 2719 5626 6320 3381 4450 6429 661 3172 2735 2267 6581 6286 7640 2440 2784 341 637 2245 7874 121 183...
output:
7752
result:
ok single line: '7752'
Test #36:
score: 41
Accepted
time: 1140ms
memory: 19376kb
input:
7996 5467 6280 6464 790 428 3075 1210 1770 2052 4187 5648 6981 7057 2971 558 2173 3654 5366 2136 6972 286 2190 4444 1578 2990 2043 5972 5748 6749 1389 7236 2776 134 1806 7567 226 3381 3995 1275 7043 745 7068 1766 5953 6379 3653 4273 1633 4817 1439 3432 3390 1936 3010 1370 3606 4519 599 4778 3249 321...
output:
7752
result:
ok single line: '7752'
Test #37:
score: 41
Accepted
time: 1184ms
memory: 19496kb
input:
7997 3305 3912 6210 2988 7049 5003 5690 59 712 7974 4251 6767 2679 5824 1317 6904 5581 5875 1938 1811 810 5241 4868 2551 7581 602 2797 2148 6639 6786 7881 627 1349 6128 2314 167 3245 1215 6694 4965 4165 2708 7702 3543 4453 4787 5361 1249 6107 3777 4955 5615 6159 7275 2707 7624 6284 1104 7826 5339 39...
output:
7754
result:
ok single line: '7754'
Test #38:
score: 41
Accepted
time: 1260ms
memory: 20080kb
input:
7998 2737 7370 3290 6547 2700 4011 6863 6031 3274 3849 7364 1162 4026 1676 7609 7340 2121 6747 2398 5962 5456 4196 2838 6376 977 2659 6589 365 839 7391 7906 3250 4234 1056 2539 1236 5449 6912 1217 3129 207 5856 5566 5184 7125 4331 53 6331 7772 2559 5830 6791 4743 6438 7928 4826 1001 1008 3161 1340 2...
output:
7751
result:
ok single line: '7751'
Test #39:
score: 41
Accepted
time: 1255ms
memory: 19276kb
input:
7999 7289 3986 1632 950 2779 4282 2869 7430 3838 6875 7342 6555 5838 5103 3613 2624 2270 6647 4356 1883 3775 982 663 4737 7993 7611 4029 3554 5711 2351 624 5121 2711 2621 3577 7385 4957 5725 5115 2579 5016 731 2584 3856 1331 7745 4679 2170 405 7581 2109 3865 5140 6787 6703 4042 2219 6154 809 6460 44...
output:
7752
result:
ok single line: '7752'
Test #40:
score: 41
Accepted
time: 1204ms
memory: 19404kb
input:
8000 718 3346 2338 3519 4215 6585 7840 5711 2140 2179 2100 3119 663 3950 562 5604 7791 5367 1715 7754 3452 7582 4906 2029 5309 483 3218 5050 3552 6409 5603 7210 2703 5136 723 821 7333 4204 557 7084 4102 539 378 7531 7350 2680 6056 3642 1938 5540 2629 4361 7591 2662 3160 4087 4423 296 4403 4522 2866 ...
output:
7756
result:
ok single line: '7756'
Extra Test:
score: 0
Extra Test Passed