C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e6+10;//两倍空间，破环成链

int n;
int o[N], d[N];
ll s[N];
bool ans[N];
int q[N*2];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%d%d", &o[i], &d[i]);
    //顺时针做
    for(int i=1;i<=n;i++) s[i]=s[i+n]=o[i]-d[i];
    for(int i=1;i<=n*2;i++) s[i] += s[i-1];

    int hh=0, tt=-1;
    for(int i=n*2; i; i--){//从后往前  因为顺时针走时需要看到i后面长度为n的区间中s的最小值
        if(hh<=tt&&q[hh]>=i+n)hh++;
        while(hh<=tt&& s[q[tt]]>=s[i])tt--;
        q[++tt]=i;//先更新再求，因为要用到s[i]
        if(i<=n){
            if(s[q[hh]]>=s[i-1])ans[i]=true;
        }

    }

    //逆时针做
    d[0]=d[n];
    for(int i=1;i<=n; i++)s[i]=s[i+n]=o[i]-d[i-1];
    for(int i=1; i<=n*2;i++)s[i]+=s[i-1];//注意这里的写法

    hh=0,tt=-1;
    for(int i=1; i<=n*2; i++){//从前往后，因为逆时针走时需要看到i前面长度为n的区间中s的最小值
        if(hh<=tt && q[hh]<i-n)hh++;
        if(i>n){
            if(s[q[hh]]<=s[i])ans[i-n]=true;
        }
        while(hh<=tt&&s[q[tt]]<=s[i])tt--;
        q[++tt]=i;
    }
    for(int i=1;i<=n;i++)
        if(ans[i])puts("TAK");
        else puts("NIE");

    return 0;
}