C++(g++ 7.5.0) 解法, 执行用时: 37ms, 内存消耗: 4600K, 提交时间: 2023-03-17 17:07:17

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+4;
long long s[2*N];
bool vs[N];
int p[N],d[N],a[2*N],q[2*N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d%d",&p[i],&d[i]);
        a[i]=a[i+n]=p[i]-d[i];
    }
    int hh=1,tt=1;
    for(int i=1;i<=2*n;i++)
    {
        s[i]=s[i-1]+a[i];
        while(hh <= tt && i - q[hh] >= n)hh++;
        while(hh <= tt && s[i] <= s[q[tt]])
            tt--;
        q[++tt] = i;
        if(i>=n&&s[q[hh]]>=s[i-n])
            vs[i-n+1]=true;
        
    }
    for(int i=1;i<n;i++)
        a[i]=a[i+n]=p[n-i+1]-d[n-i];
    a[n]=p[1]-d[n];
    hh = 1, tt = 0;
    for(int i=1;i<=2*n;i++)
    {
        s[i]=s[i-1]+a[i];
        while(hh <= tt && i - q[hh] >= n)hh++;
        while(hh <= tt && s[i] <= s[q[tt]])
            tt--;
        q[++tt] = i;
        if(i>=n&&s[q[hh]]>=s[i-n])
            vs[2*n-i]=true;
    }
    for(int i=1;i<=n;i++) 
        if(vs[i])
            puts("TAK");
        else
            puts("NIE");
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 31ms, 内存消耗: 3916K, 提交时间: 2020-08-04 09:12:40

#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=3e6+10;
bool ans[N][2];
int n,p[N],d[N];
long long dp[6000000];
deque<long long>q;
void around(int id){
	for(int i=1;i<n;i++){
		dp[i+n]=dp[i],dp[i]+=dp[i-1];
		while(!q.empty()&&dp[i]<q.back())
			q.pop_back();
		q.push_back(dp[i]);
	}for(int i=0,j=n;i<n;i++,j++){
		dp[j]+=dp[j-1];
		while(!q.empty()&&dp[j]<q.back())
			q.pop_back();
		q.push_back(dp[j]);
		if(i&&q.front()==dp[i])q.pop_front();
		if(q.front()>=dp[i])ans[i][id]=true;
	}q.clear();
}int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
		scanf("%d%d",p+i,d+i),dp[i]=p[i]-d[i];
	around(0),d[0]=d[n];
	for(int i=1;i<=n;i++)
		dp[i]=p[n+1-i]-d[n-i];
	around(1); 
	for(int i=0;i<n;i++)
		puts((ans[i][0]||ans[n-i-1][1])?"TAK":"NIE");
	return 0;
}