QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152759#4906. 球球zhouhuanyi0 5ms43388kbC++143.9kb2023-08-28 19:42:582023-08-28 19:42:58

Judging History

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

  • [2023-08-28 19:42:58]
  • 评测
  • 测评结果:0
  • 用时:5ms
  • 内存:43388kb
  • [2023-08-28 19:42:58]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#define N 1000001
#define M 1048575
using namespace std;
const long long inf=(long long)(1e18);
const int INF=(int)(1e9);
char buf[N+1],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?0:*p1++)
int read()
{
    char c=0;
    int sum=0,f=1;
    while (c!='-'&&(c<'0'||c>'9')) c=gc();
    if (c=='-') c=gc(),f=-1;
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=gc();
    return sum*f;
}
void Adder(long long &x,long long d)
{
    x=(x<d)?x:d;
    return;
}
struct reads
{
    long long t,x;
};
reads st[N+1];
struct node
{
    int l,r,d;
    bool operator < (const node &t)const
	{
		return r<t.r;
	}
};
struct rds
{
    int num,data;
};
struct ed
{
	int num,data,nxt;
};
ed edge[M+1];
int n,len,L[N+1],lst[N+1],nt[N+1],head[M+1];
long long dp[N+1][2];
set<node>s;
vector<rds>v[N+1];
void adder(int l,int r,int d)
{
    if (l>r) return;
    node top;
    for (auto it=s.lower_bound((node){0,l});(*it).l<=r&&it!=s.end();it=s.lower_bound((node){0,l}))
    {
		top=(*it),s.erase(it);
		if (top.l<=l-1) s.insert((node){top.l,l-1,top.d});
		if (r+1<=top.r) s.insert((node){r+1,top.r,top.d});
    }
    s.insert((node){l,r,d});
    return;
}
int query(int x)
{
    auto it=s.lower_bound((node){0,x,0});
    return (*it).d;
}
void adder2(int x,int d)
{
	int ds=(x+INF)&M;
	for (int i=head[ds];i>0;i=edge[i].nxt)
		if (edge[i].num==x)
		{
			edge[i].data=max(edge[i].data,d);
			return;
		}
	edge[++len]=(ed){x,d,head[ds]},head[ds]=len;
	return;
}
int query2(int x)
{
	int ds=(x+INF)&M;
	for (int i=head[ds];i>0;i=edge[i].nxt)
		if (edge[i].num==x)
			return edge[i].data;
	return 0;
}
int main()
{
    long long d;
	int l,r,sl,sr,ps,ps2;
    n=read(),s.insert((node){-INF,INF,0});
    for (int i=1;i<=n;++i) st[i].t=read(),st[i].x=read(),L[i]=1;
    for (int i=0;i<=n;++i) dp[i][0]=dp[i][1]=inf;
    for (int i=1;i<=n;++i)
    {
		if (st[i].x==st[i-1].x) lst[i]=lst[i-1];
		else lst[i]=i-1;
    }
    nt[n+1]=n+1;
    for (int i=n;i>=1;--i)
    {
		if (st[i+1].x==st[i].x) nt[i]=nt[i+1];
		else nt[i]=i+1;
    }
    for (int i=2;i<=n;++i)
    {
		L[i]=max(max(L[i],query(st[i].x)),query2(st[i].x));
		if (lst[i-1]&&st[i-1].x!=st[i].x&&st[lst[i-1]].x!=st[i-1].x&&abs(st[i].x-st[lst[i-1]].x)>st[i].t-st[lst[i-1]].t) adder2(st[i-1].x,lst[i-1]+1);
		if (abs(st[i-1].x-st[i].x)>st[i].t-st[i-1].t) adder(-INF,min(st[i-1].x,st[i].x)-1,i),adder(min(st[i-1].x,st[i].x)+1,max(st[i-1].x,st[i].x)-1,i),adder(max(st[i-1].x,st[i].x)+1,INF,i);
    }
	for (int i=0;i<M;++i) head[i]=0;
    s.clear(),s.insert((node){-INF,INF,0}),dp[0][0]=0;
    for (int i=0;i<=n;++i)
    {
		for (int j=0;j<v[i].size();++j) adder2(v[i][j].num,v[i][j].data);
		if (dp[lst[i]][0]+abs(st[lst[i]].x-st[i].x)<=st[lst[i]+1].t) Adder(dp[i][0],max(dp[lst[i]][0]+abs(st[lst[i]].x-st[i].x),st[lst[i]].t));
		if (dp[lst[i]][1]+abs(st[lst[lst[i]]].x-st[i].x)<=st[lst[i]+1].t) Adder(dp[i][0],max(dp[lst[i]][1]+abs(st[lst[lst[i]]].x-st[i].x),st[lst[i]].t));
		if (max(query(st[i].x),query2(st[i].x))>=L[i]) dp[i][1]=st[lst[i]].t;
		//0
		if (i+1<=n)
		{
			ps=i+1,l=st[ps].x-(st[ps].t-st[i].t),r=st[ps].x+(st[ps].t-st[i].t);
			if (min(dp[i][0],dp[i][1])+abs(st[i].x-st[ps].x)<=st[ps].t)
			{
				d=(st[ps].t-abs(st[i].x-st[ps].x)-min(dp[i][0],dp[i][1]))>>1,sl=max(min(st[i].x,st[ps].x)-d,(long long)(l)),sr=min(max(st[i].x,st[ps].x)+d,(long long)(r));
				if (st[ps].x<sl||st[ps].x>sr) adder(sl,sr,i+1);
				else adder(sl,st[ps].x-1,i+1),adder(st[ps].x+1,sr,i+1);
			}
		}
		//1
		if (nt[i+1]<=n)
		{
			ps=nt[i+1],ps2=i+1;
			if (min(dp[i][0],dp[i][1])+abs(st[i].x-st[ps2].x)<=st[ps2].t&&max(min(dp[i][0],dp[i][1])+abs(st[i].x-st[ps2].x),st[i].t)+abs(st[ps2].x-st[ps].x)<=st[ps].t) v[ps+1].push_back((rds){st[ps2].x,i+1});
		}
    }
    puts((dp[n][0]!=inf||dp[n][1]!=inf)?"YES":"NO");
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 5ms
memory: 41976kb

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

input:

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

output:

NO

result:

ok single line: 'NO'

Test #3:

score: -5
Wrong Answer
time: 4ms
memory: 42896kb

input:

4
16 13
18 4
20 3
21 5

output:

YES

result:

wrong answer 1st lines differ - expected: 'NO', found: 'YES'

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: 0
Wrong Answer
time: 4ms
memory: 42840kb

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:

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%