QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188761 | #4906. 球球 | Crysfly | 0 | 5ms | 24188kb | C++20 | 2.3kb | 2023-09-26 13:31:29 | 2023-09-26 13:31:31 |
Judging History
answer
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 1000005
#define inf 0x3f3f3f3f
int n,x[maxn],t[maxn];
int can[maxn],pre[maxn],pos[maxn];
int fir[maxn];
int f[maxn],g[maxn];
int dis(int i,int j){return abs(x[i]-x[j]);}
unordered_map<int,int>tmp;
signed main()
{
n=read();
For(i,1,n)t[i]=read(),x[i]=read(),f[i]=g[i]=inf;
For(i,1,n){
can[i]=can[i-1]+(t[i-1]+dis(i,i-1)>t[i]);
pre[i]=i;
if(i>1 && x[i-1]==x[i])pre[i]=pre[i-1];
}
memset(fir,-1,sizeof fir);
For(i,0,n)
if(fir[can[i]]==-1) fir[can[i]]=i;
f[0]=g[0]=0;
pos[0]=0;
For(i,1,n)pos[i]=max(0ll,pre[i]-1);
/*
put clone at x[i],get [0,pos[i]]
f[i] : self take pos[i]
g[i] : clone take pos[i]
*/
For(i,1,n){
For(j,fir[can[i-1]]-1,i-2)
if(1){
if(x[i]!=x[j]){
int tim=max(t[j],max(f[j]+dis(i,j),t[pos[j]]+dis(pos[j],i)));
if(tim+dis(i,j+1)<=t[j+1]) f[i]=min(f[i],tim);
tim=max(t[j],g[j]+dis(i,j));
if(tim+dis(i,j+1)<=t[j+1]) f[i]=min(f[i],tim);
}
if(f[i]<inf)break;
}
if(tmp.count(x[i])) f[i]=min(f[i],tmp[x[i]]);
if(x[i-1]==x[i]){
f[i]=min(f[i],f[i-1]);
g[i]=min(g[i],g[i-1]);
}else{
g[i]=min(g[i],max(t[i-1],g[i-1]+dis(i-1,i)));
g[i]=min(g[i],max(max(t[i-1],t[pos[i-1]]+dis(pos[i-1],i)),f[i-1]+dis(i-1,i)));
}
if(f[i]>t[i])f[i]=inf;
if(g[i]>t[i])g[i]=inf;
if(i-1!=n){
int j=i-1;
if(g[j]+dis(j,j+1)<=t[j+1]) tmp[x[i]]=min(tmp[x[i]],g[i]);
if(max(f[j]+dis(j,j+1),t[pos[j]]+dis(pos[j],j+1))<=t[j+1]) tmp[x[i]]=min(tmp[x[i]],f[i]);
}
// cout<<f[i]<<" "<<g[i]<<"\n";
}
if(min(f[n],g[n])<inf)puts("YES");
else puts("NO");
return 0;
}
/*
11
1 1
2 1
3 1
4 -2
6 -2
6 1
8 1
11 5
11 1
13 5
14 2
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 21856kb
input:
5 2 1 3 2 9 6 10 5 13 -1
output:
NO
result:
ok single line: 'NO'
Test #2:
score: 0
Accepted
time: 4ms
memory: 21884kb
input:
5 1 1 3 2 4 -1 6 4 10 -1
output:
NO
result:
ok single line: 'NO'
Test #3:
score: 0
Accepted
time: 3ms
memory: 19912kb
input:
4 16 13 18 4 20 3 21 5
output:
NO
result:
ok single line: 'NO'
Test #4:
score: 0
Accepted
time: 0ms
memory: 21892kb
input:
5 2 1 3 2 8 6 10 5 13 0
output:
YES
result:
ok single line: 'YES'
Test #5:
score: -5
Wrong Answer
time: 3ms
memory: 19884kb
input:
5 2 1 3 2 9 6 10 5 13 0
output:
NO
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #91:
score: 20
Accepted
time: 0ms
memory: 20088kb
input:
5000 6 6 80 80 170 48 240 106 243 179 329 176 412 93 485 176 552 249 555 316 613 371 650 313 733 251 735 253 736 334 815 254 893 333 943 255 965 227 1022 284 1116 205 1174 320 1230 376 1318 378 1336 288 1430 212 1494 276 1562 344 1597 309 1638 350 1716 272 1793 349 1809 365 1908 306 1951 464 2037 42...
output:
YES
result:
ok single line: 'YES'
Test #92:
score: 0
Accepted
time: 0ms
memory: 20024kb
input:
5000 64 -64 146 -46 177 -14 249 -5 327 -77 370 -83 438 -194 463 -219 554 -126 625 -199 689 -128 774 -50 854 -135 882 2 916 30 936 -12 1022 -98 1071 -32 1157 -49 1195 75 1206 37 1221 86 1227 77 1251 71 1269 101 1324 83 1373 28 1426 77 1439 24 1454 11 1508 -4 1601 35 1619 -58 1668 17 1719 -32 1775 -37...
output:
YES
result:
ok single line: 'YES'
Test #93:
score: 0
Accepted
time: 2ms
memory: 22080kb
input:
5000 136 32 137 31 188 82 248 142 266 -52 277 124 327 135 370 185 445 153 506 228 536 214 586 194 652 128 685 244 778 95 812 2 884 108 917 141 984 36 989 208 1012 190 1042 213 1078 220 1139 184 1204 245 1205 311 1208 310 1282 382 1363 463 1383 308 1449 443 1470 530 1531 509 1560 591 1588 620 1623 55...
output:
YES
result:
ok single line: 'YES'
Test #94:
score: 0
Accepted
time: 4ms
memory: 20052kb
input:
5000 17 17 116 -44 157 -3 224 -63 279 64 320 119 328 78 365 33 367 35 447 70 473 89 554 115 602 122 664 184 683 170 689 159 760 165 763 85 788 88 793 60 795 65 854 8 855 9 910 -46 911 -45 995 39 1070 -36 1147 41 1191 -3 1284 67 1367 -179 1419 -127 1442 -96 1475 -104 1480 -142 1575 -237 1657 -155 167...
output:
YES
result:
ok single line: 'YES'
Test #95:
score: 0
Accepted
time: 5ms
memory: 22140kb
input:
5000 60 -49 67 -60 96 -82 99 -85 128 -53 144 -72 239 -56 269 -137 305 -101 309 -167 324 -105 362 -82 428 -120 498 54 590 -38 688 -16 760 60 787 132 855 105 862 180 944 98 997 173 1023 71 1095 45 1174 64 1213 143 1285 31 1360 103 1446 -130 1480 -96 1564 -44 1577 1 1584 8 1598 22 1669 -12 1707 -87 171...
output:
YES
result:
ok single line: 'YES'
Test #96:
score: 0
Accepted
time: 0ms
memory: 22096kb
input:
5000 142 -77 231 -12 278 -54 323 -99 392 -101 449 -30 454 27 537 22 633 -61 688 -102 701 -157 755 -169 756 -170 819 -107 914 -115 976 -12 1048 -146 1115 -74 1134 -213 1203 -301 1222 -282 1313 -232 1366 -191 1417 -193 1437 -244 1529 -121 1628 -220 1668 -213 1714 -134 1775 -73 1820 -180 1898 -28 1959 ...
output:
YES
result:
ok single line: 'YES'
Test #97:
score: 0
Accepted
time: 2ms
memory: 22108kb
input:
5000 54 54 110 -2 131 34 184 -34 227 9 301 19 394 -65 488 28 567 122 661 295 675 201 676 281 706 252 757 282 851 209 889 303 921 215 1016 247 1059 267 1134 310 1196 192 1201 249 1251 254 1340 210 1422 128 1457 163 1467 153 1564 250 1632 318 1683 299 1708 369 1736 316 1786 266 1811 291 1812 344 1816 ...
output:
YES
result:
ok single line: 'YES'
Test #98:
score: 0
Accepted
time: 5ms
memory: 24100kb
input:
5000 78 78 172 94 185 39 205 81 211 101 245 61 332 95 334 -24 370 12 442 84 452 -26 533 94 581 13 639 -93 722 -35 771 -10 835 -59 923 -123 948 -35 971 -60 1047 39 1048 40 1078 10 1081 7 1087 1 1146 -58 1170 -82 1264 -37 1351 -176 1352 -264 1359 -263 1455 -257 1479 -185 1496 -161 1512 -202 1601 -218 ...
output:
YES
result:
ok single line: 'YES'
Test #99:
score: 0
Accepted
time: 0ms
memory: 22136kb
input:
5000 28 -10 29 -28 120 -27 161 -159 240 -238 275 -203 362 -290 393 -118 456 -258 461 -321 475 -263 571 -373 648 -277 737 -361 803 -427 852 -450 921 -545 993 -473 1042 -476 1097 -522 1130 -434 1190 -494 1229 -467 1328 -455 1427 -554 1511 -455 1572 -310 1664 -371 1717 -218 1769 -165 1866 -314 1927 -37...
output:
YES
result:
ok single line: 'YES'
Test #100:
score: 0
Accepted
time: 0ms
memory: 22084kb
input:
5000 18 18 98 -62 183 23 211 -31 295 51 334 -33 368 6 457 40 543 -135 633 -49 699 -225 781 -159 793 -77 807 -75 816 -89 829 -79 845 -95 863 -113 948 -198 982 -66 1011 -232 1029 -203 1073 -221 1118 -265 1147 -310 1242 -339 1319 -167 1413 -244 1486 0 1556 -73 1637 151 1688 202 1734 156 1765 187 1767 1...
output:
YES
result:
ok single line: 'YES'
Test #101:
score: 0
Accepted
time: 0ms
memory: 22132kb
input:
5000 49 49 174 -41 202 -6 296 22 313 116 403 43 486 133 560 -40 623 -114 697 -177 781 -251 852 -335 912 -204 1005 -111 1068 -264 1162 -48 1216 100 1236 46 1275 159 1303 187 1380 120 1446 110 1508 -18 1595 44 1668 -4 1758 69 1826 86 1834 162 1860 136 1891 154 1969 105 2042 27 2130 100 2188 130 2281 2...
output:
YES
result:
ok single line: 'YES'
Test #102:
score: 0
Accepted
time: 0ms
memory: 22180kb
input:
5000 100 84 114 92 153 70 245 201 296 109 325 150 351 179 416 88 453 153 456 51 479 48 574 25 624 -20 695 -91 733 -70 781 -129 841 -141 879 -179 949 -81 973 -85 1040 -152 1054 -109 1102 -214 1150 -262 1159 -166 1255 -349 1278 -253 1365 -326 1371 -407 1468 -504 1524 -448 1596 -520 1597 -413 1676 -598...
output:
YES
result:
ok single line: 'YES'
Test #103:
score: 0
Accepted
time: 4ms
memory: 20008kb
input:
5000 45 -45 90 -64 109 -90 160 -58 161 -59 254 -109 268 -138 319 -152 377 -29 456 -108 500 -87 524 -64 543 -59 572 -40 606 -122 653 -169 657 -173 735 -95 777 -88 869 -137 878 -45 946 -36 1012 -104 1049 -38 1055 -7 1108 46 1201 -1 1286 139 1302 224 1344 240 1394 282 1472 232 1508 310 1554 392 1644 30...
output:
YES
result:
ok single line: 'YES'
Test #104:
score: 0
Accepted
time: 0ms
memory: 22072kb
input:
5000 50 50 141 -41 177 -27 235 9 275 -49 353 47 424 -31 441 101 526 186 537 118 588 197 603 248 696 326 785 233 831 415 862 369 870 338 928 330 1014 388 1055 261 1064 252 1091 279 1155 215 1201 302 1299 359 1305 261 1352 353 1392 400 1446 494 1527 413 1583 357 1606 334 1662 440 1710 342 1767 399 183...
output:
YES
result:
ok single line: 'YES'
Test #105:
score: 0
Accepted
time: 0ms
memory: 20092kb
input:
5000 92 92 163 159 177 161 198 145 275 243 342 310 404 248 502 166 569 279 597 346 696 251 728 152 731 123 819 120 842 188 852 211 927 253 943 178 1004 176 1047 219 1139 311 1191 259 1288 356 1354 237 1444 422 1483 332 1492 371 1516 362 1520 334 1554 338 1591 263 1606 300 1666 278 1754 338 1851 426 ...
output:
YES
result:
ok single line: 'YES'
Test #106:
score: 0
Accepted
time: 0ms
memory: 24188kb
input:
5000 137 -43 221 41 239 59 275 23 313 61 360 -90 447 14 463 -57 509 -73 514 -6 525 -11 559 -17 603 -95 681 -173 761 -253 850 -164 891 -123 894 -51 914 -126 975 -207 1060 -122 1066 -146 1103 -116 1127 -153 1225 -275 1236 -286 1280 -177 1358 -408 1372 -330 1457 -337 1532 -412 1620 -500 1624 -496 1702 ...
output:
YES
result:
ok single line: 'YES'
Test #107:
score: 0
Accepted
time: 0ms
memory: 22140kb
input:
5000 84 -84 150 -72 204 -18 206 -72 292 -70 343 -105 428 -156 465 -57 548 -20 563 -140 619 -69 691 -125 774 3 789 -65 811 -43 894 -80 990 -56 1040 40 1059 -106 1151 -125 1182 -217 1246 -186 1268 -250 1277 -272 1361 -197 1384 -220 1386 -281 1433 -222 1449 -269 1473 -277 1564 -368 1571 -361 1586 -253 ...
output:
YES
result:
ok single line: 'YES'
Test #108:
score: 0
Accepted
time: 0ms
memory: 22052kb
input:
5000 80 -80 129 -129 149 -109 208 -168 239 -137 251 -125 340 -214 409 -145 539 -135 586 -205 593 -81 685 -88 741 -45 768 -18 835 11 872 49 965 86 1043 179 1047 101 1052 100 1069 117 1084 105 1116 164 1180 132 1231 228 1302 208 1310 200 1381 129 1442 279 1443 191 1500 134 1505 190 1602 236 1644 139 1...
output:
YES
result:
ok single line: 'YES'
Test #109:
score: 0
Accepted
time: 0ms
memory: 22140kb
input:
5000 59 59 76 76 107 45 125 63 179 9 242 42 318 72 381 59 461 139 545 -4 643 125 730 223 805 212 825 307 914 287 927 396 940 383 983 327 1057 370 1089 253 1120 221 1200 332 1294 252 1299 243 1370 314 1422 238 1509 175 1576 262 1613 108 1680 78 1719 39 1767 87 1854 0 1886 145 1890 28 1938 -20 2004 46...
output:
YES
result:
ok single line: 'YES'
Test #110:
score: 0
Accepted
time: 4ms
memory: 24156kb
input:
5000 134 -32 169 -83 170 -66 251 -67 330 15 340 104 389 94 449 213 474 188 562 153 630 208 658 236 721 299 739 281 798 340 843 276 853 375 856 372 864 385 907 364 965 379 1018 321 1071 432 1166 474 1168 379 1236 544 1243 551 1245 476 1316 624 1331 553 1396 574 1424 602 1496 530 1505 521 1542 639 157...
output:
YES
result:
ok single line: 'YES'
Test #111:
score: -20
Wrong Answer
time: 0ms
memory: 22124kb
input:
5000 22 22 116 -46 159 -72 240 -29 278 14 362 52 432 0 499 67 579 -70 595 163 648 147 688 70 707 110 776 120 785 111 833 159 903 51 979 229 1033 305 1083 301 1084 251 1128 302 1174 258 1265 395 1330 460 1396 304 1415 394 1450 378 1451 379 1463 367 1499 403 1500 404 1508 413 1598 396 1652 540 1699 48...
output:
YES
result:
wrong answer 1st lines differ - expected: 'NO', found: 'YES'
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #4:
0%
Subtask #8:
score: 0
Skipped
Dependency #7:
0%