QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149587 | #4906. 球球 | zhouhuanyi | 0 | 5ms | 55048kb | C++14 | 3.9kb | 2023-08-24 22:24:25 | 2023-08-24 22:24:28 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<cassert>
#define N 2000000
#define inf 1e18
#define INF 1e9
using namespace std;
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=getchar(),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;
};
int n,L[N+1],lst[N+1],nt[N+1];
long long dp[N+1][2];
set<node>s;
map<int,int>p;
vector<rds>v[N+1];
void adder(int l,int r,int d)
{
if (l>r) return;
int L,R,ds;
for (auto it=s.lower_bound((node){0,l,0});(*it).l<=r&&it!=s.end();it=s.lower_bound((node){0,l,0}))
{
L=(*it).l,R=(*it).r,ds=(*it).d,s.erase(it);
if (L<=l-1) s.insert((node){L,l-1,ds});
if (r+1<=R) s.insert((node){r+1,R,ds});
}
s.insert((node){l,r,d});
return;
}
int query(int x)
{
auto it=s.lower_bound((node){0,x,0});
return (*it).d;
}
int main()
{
long long d,l,r,sl,sr,ps,ps2;
n=read(),s.insert((node){(int)(-INF),(int)(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)),p[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) p[st[i-1].x]=max(p[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);
}
p.clear(),s.clear(),s.insert((node){(int)(-INF),(int)(INF),0}),dp[0][0]=0;
for (int i=0;i<=n;++i)
{
for (int j=0;j<v[i].size();++j) p[v[i][j].num]=max(p[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),p[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 (dp[i][0]+abs(st[i].x-st[ps].x)<=st[ps].t)
{
d=(st[ps].t-abs(st[i].x-st[ps].x)-dp[i][0])>>1,sl=max(min(st[i].x,st[ps].x)-d,l),sr=min(max(st[i].x,st[ps].x)+d,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);
}
if (dp[i][1]+abs(st[lst[i]].x-st[ps].x)<=st[ps].t)
{
d=(st[ps].t-abs(st[lst[i]].x-st[ps].x)-dp[i][1])>>1,sl=max(min(st[lst[i]].x,st[ps].x)-d,l),sr=min(max(st[lst[i]].x,st[ps].x)+d,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 (dp[i][0]+abs(st[i].x-st[ps2].x)<=st[ps2].t&&max(dp[i][0]+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});
if (dp[i][1]+abs(st[lst[i]].x-st[ps2].x)<=st[ps2].t&&max(dp[i][1]+abs(st[lst[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: 0
Wrong Answer
time: 4ms
memory: 52996kb
input:
5 2 1 3 2 9 6 10 5 13 -1
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: 5ms
memory: 55048kb
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%