QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188760#4906. 球球Crysfly0 5ms24296kbC++202.3kb2023-09-26 13:30:432023-09-26 13:30:43

Judging History

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

  • [2023-09-26 13:30:43]
  • 评测
  • 测评结果:0
  • 用时:5ms
  • 内存:24296kb
  • [2023-09-26 13:30:43]
  • 提交

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!=n){
			int j=i;
			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: 22080kb

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: 3ms
memory: 22264kb

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: 21976kb

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: 22232kb

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: 22040kb

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: 3ms
memory: 22212kb

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: 20432kb

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: 22180kb

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: 0ms
memory: 24172kb

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: 24272kb

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: 22220kb

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: 4ms
memory: 22244kb

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: 0ms
memory: 22260kb

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: 4ms
memory: 20088kb

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: 4ms
memory: 22256kb

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: 22248kb

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: 2ms
memory: 22232kb

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: 3ms
memory: 20348kb

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: 22392kb

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: 22264kb

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: 22188kb

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: 5ms
memory: 24296kb

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: 24232kb

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: 22392kb

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: 0ms
memory: 22248kb

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: 22140kb

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%