之前的一个求助帖。

和上面这个人错得一样，但是我搜了提交记录却发现没有他的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
const int N=4e6+5;

int n;
LL p[N],d[N],a[N]; 
LL sum[N];
bool ans[N];
deque<int> q;

signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&p[i],&d[i]);
		a[i]=p[i]-d[i]; 
		a[i+n]=a[i];
	}
	for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
	
	q.push_back(0);
	
	for(int i=1;i<2*n;i++){
		while(q.size() && q.front()<=i-n) q.pop_front();
		if(i>=n){
			if(sum[q.front()] - sum[i-n] >= 0)
				ans[i-n+1]=1;
		}
		while(q.size() && sum[q.back()] > sum[i]) q.pop_back();
		q.push_back(i);
	}
	
	//------------------------------------------------------------------
	p[0]=p[n]; d[0]=d[n];
	for(int i=1;i<=n;i++){
		a[i]=p[i]-d[i-1]; 
		a[i+n]=a[i];
	}
	for(int i=2*n;i>=1;i--) sum[i]=sum[i+1]+a[i];
	
	q.clear();
	q.push_back(2*n+1);
	
	for(int i=2*n;i>1;i--){
		while(q.size() && q.front()>=i+n) q.pop_front();
		if(i<=n+1){
			if(sum[q.front()] - sum[i+n] >= 0)
				ans[i-1]=1;
		}
		while(q.size() && sum[q.back()] > sum[i]) q.pop_back();
		q.push_back(i);
	}	
	
	//--------------------------------------------------------------
	for(int i=1;i<=n;i++){
		if(ans[i]) printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}