QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#188757 | #4906. 球球 | Crysfly | 0 | 5ms | 26232kb | C++20 | 2.6kb | 2023-09-26 13:26:56 | 2023-09-26 13:26:56 |
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]);}
int ids[maxn],tmp[maxn];
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];
}
For(i,1,n)ids[i]=ids[i-1]+(x[i]!=x[i-1]);
For(i,0,n)tmp[i]=inf;
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);
}else{
// if(g[j]+dis(j,j+1)<=t[j+1]) f[i]=min(f[i],g[j]);
// if(max(f[j]+dis(j,j+1),t[pos[j]]+dis(pos[j],j+1))<=t[j+1]) f[i]=min(f[i],f[j]);
f[i]=min(f[i],tmp[ids[i]]);
break;
}
if(f[i]<inf)break;
}
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;
{
int j=i;
if(g[j]+dis(j,j+1)<=t[j+1]) tmp[ids[i]]=min(tmp[ids[i]],g[i]);
if(max(f[j]+dis(j,j+1),t[pos[j]]+dis(pos[j],j+1))<=t[j+1]) tmp[ids[i]]=min(tmp[ids[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
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 23872kb
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: 0ms
memory: 21880kb
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: 0ms
memory: 23944kb
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: 24088kb
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: 0ms
memory: 23904kb
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: 5ms
memory: 26004kb
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: 22084kb
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: 0ms
memory: 24116kb
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: 2ms
memory: 26028kb
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: 0ms
memory: 26232kb
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: 24028kb
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: 0ms
memory: 26068kb
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: -20
Wrong Answer
time: 5ms
memory: 23976kb
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:
NO
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'
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%