QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188787 | #4906. 球球 | Crysfly | 0 | 5ms | 22048kb | C++20 | 3.2kb | 2023-09-26 14:19:31 | 2023-09-26 14:19:31 |
Judging History
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]
*/
auto addt=[&](int x,int y){
if(tmp.count(x))tmp[x]=min(tmp[x],y);
else tmp[x]=y;
};
auto add=[&](int j){
if(g[j]+dis(j,j+1)<=t[j+1]) addt(x[j],g[j]);
if(max(f[j]+dis(j,j+1),t[pos[j]]+dis(pos[j],j+1))<=t[j+1]) addt(x[j],f[j]);
};
set<pii>s;
int p=1;
For(i,1,n){
if(i>1 && can[i-1]!=can[i-2]) tmp.clear();
if(i>1) add(i-2);
if(tmp.count(x[i])) f[i]=min(f[i],tmp[x[i]]);
// For(j,fir[can[i-1]]-1,i-2){
// 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(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;
while(p<=n && can[p-1]<=can[i+1]){
++p;
if(p>=i+2) s.insert(mkp(x[p],p));
}
auto trs=[&](int j,int i){
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);
return f[i]<inf;
};
for(int xx:{x[i],x[i+1],x[pos[i]]}){
while(1){
auto it=s.lower_bound(mkp(xx,-1));
if(it==s.end())break;
if(it->se<i+2 || can[i+1]!=can[it->se-1]) s.erase(it);
else if(trs(i,it->se)) s.erase(it);
else break;
}
while(1){
auto it=s.lower_bound(mkp(xx,-1));
if(it==s.begin())break;
--it;
if(it->se<i+2 || can[i+1]!=can[it->se-1]) s.erase(it);
else if(trs(i,it->se)) s.erase(it);
else break;
}
}
}
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: 22048kb
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: 21336kb
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: 20224kb
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: 17524kb
input:
5 2 1 3 2 8 6 10 5 13 0
output:
YES
result:
ok single line: 'YES'
Test #5:
score: 0
Accepted
time: 0ms
memory: 21356kb
input:
5 2 1 3 2 9 6 10 5 13 0
output:
YES
result:
ok single line: 'YES'
Test #6:
score: 0
Accepted
time: 0ms
memory: 19564kb
input:
5 1 1 3 2 4 0 6 4 10 -1
output:
YES
result:
ok single line: 'YES'
Test #7:
score: 0
Accepted
time: 0ms
memory: 20308kb
input:
3 1 0 5 5 6 2
output:
YES
result:
ok single line: 'YES'
Test #8:
score: 0
Accepted
time: 5ms
memory: 19868kb
input:
5 2 1 6 0 7 -1 8 2 9 -2
output:
YES
result:
ok single line: 'YES'
Test #9:
score: -5
Wrong Answer
time: 0ms
memory: 19628kb
input:
5 30 10 40 -10 51 9 52 8 53 20
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: 0
Wrong Answer
time: 0ms
memory: 20532kb
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%