QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188758#4906. 球球Crysfly0 0ms24124kbC++202.6kb2023-09-26 13:28:042023-09-26 13:28:04

Judging History

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

  • [2023-09-26 13:28:04]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:24124kb
  • [2023-09-26 13:28:04]
  • 提交

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]);
					assert(ids[j]==ids[i]);
					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;
		if(i!=n){
			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
*/

詳細信息

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 5
Accepted
time: 0ms
memory: 24124kb

input:

5
2 1
3 2
9 6
10 5
13 -1

output:

NO

result:

ok single line: 'NO'

Test #2:

score: -5
Runtime Error

input:

5
1 1
3 2
4 -1
6 4
10 -1

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #91:

score: 0
Runtime Error

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:


result:


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%