8.10XS模拟赛

8.11 A

A

洛谷P3422

XS评测记1e6的st表超时，洛谷线段树都可以过

于是我气急败坏的写了O(n)的双端队列题解简直就是shi山

接下来是题解：

看到环，很容易想到复制一遍数组把长度变成2n来做

然后做前缀和sum，到达某个点的油量必须大于零，得到sum[i+j]-sum[i-1]>=0(0<=i<n)

变形，得到sum[i+j]>=sum[i-1]，所以只要区间内的最小值大于sum[i-1]就可以了

记得顺时针和逆时针都要跑一遍

无脑的最小值可以用st表写，但最优解是双端队列的O(n)虽然没什么用

#include<bits/stdc++.h>
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
#define fst first
#define sec second
using namespace std;
typedef long long LL;
typedef pair<int,LL> auther;
const int maxn=1e6+5;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=x*10+c-48;x=(f ? -x : x);return;
}
void read(char& c){do{c=getchar();}while(c==10||c==13);
}
int n;
int a[maxn],b[maxn];
bool ans[maxn];
LL sum[maxn<<1];
deque<auther> q;
int main(){read(n);for(int i=1;i<=n;i++){read(a[i]),read(b[i]);}for(int i=1;i<=n;i++){sum[i]=sum[i-1]+a[i]-b[i];}for(int i=1;i<=n;i++){sum[n+i]=sum[n+i-1]+a[i]-b[i];}for(int i=1;i<=n;i++){while((!q.empty())&&q.back().sec>=sum[i]) q.pop_back();q.push_back(make_pair(i,sum[i]));}for(int i=1;i<=n;i++){while((!q.empty())&&q.front().fst<i) q.pop_front();LL mn=q.front().sec;if(mn>=sum[i-1]) ans[i]|=1;while((!q.empty())&&q.back().sec>=sum[n+i]) q.pop_back();q.push_back(make_pair(n+i-1,sum[n+i]));}q.clear();for(int i=n;i>=1;i--){sum[n+i]=sum[n+i+1]+a[i]-b[i==1 ? n : i-1];}for(int i=n;i>=1;i--){sum[i]=sum[i+1]+a[i]-b[i==1 ? n : i-1];}for(int i=2;i<=n+1;i++){while((!q.empty())&&q.back().sec>=sum[i]) q.pop_back();q.push_back(make_pair(i,sum[i]));}for(int i=1;i<=n;i++){while((!q.empty())&&q.front().fst<i+1) q.pop_front();LL mn=q.front().sec;if(mn>=sum[n+i+1]) ans[i]|=1;while((!q.empty())&&q.back().sec>=sum[n+i+1]) q.pop_back();q.push_back(make_pair(n+i+1,sum[n+i+1]));}for(int i=1;i<=n;i++){if(ans[i]) printf("TAK\n");else printf("NIE\n");}return 0;
}
//^o^