QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188757#4906. 球球Crysfly0 5ms26232kbC++202.6kb2023-09-26 13:26:562023-09-26 13:26:56

Judging History

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

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

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%