AcWing 1088. 旅行问题
原题链接
中等
作者:
wangyj
,
2021-01-22 08:58:46
,
所有人可见
,
阅读 419
#include<iostream>
#include<algorithm>
using namespace std;
int n,oil[2000005],dist[2000005],q[2000005];
long long s[2000005];
bool ans[2000005];
int main()
{
int i,h=0,t=0;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d",&oil[i],&dist[i]),s[i]=s[i+n]=oil[i]-dist[i];
for(i=1;i<=n*2;i++)s[i]+=s[i-1];
q[0]=n*2+1;
for(i=n*2;i>=0;i--){
if(q[h]>i+n)h++;
if(i<n&&s[i]<=s[q[h]])ans[i+1]=true;
while(h<=t&&s[q[t]]>=s[i])t--;
q[++t]=i;
}
dist[0]=dist[n];
for(i=1;i<=n;i++)s[i]=s[i+n]=oil[i]-dist[i-1];
for(i=1;i<=n*2;i++)s[i]+=s[i-1];
h=t=q[0]=0;
for(i=1;i<=n*2;i++){
if(q[h]<i-n)h++;
if(i>n&&s[i]>=s[q[h]])ans[i-n]=true;
while(h<=t&&s[q[t]]<=s[i])t--;
q[++t]=i;
}
for(i=1;i<=n;i++)if(ans[i])printf("TAK\n");else printf("NIE\n");
return 0;
}