题目

提交记录

#include<bits/stdc++.h>
using namespace std;
const int N = 2000100;
struct node{
	int id,sum;
} q[N][2];//单调队列
int oil[N][2][2], minn[N][2];//oil[点][顺时针/逆时针][加油/耗油],minn[点][顺时针/逆时针]
int sum[N][2],n,len[2],ans[2]={1,1},a,b;//len==tail,ans==head
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&a,&b);
		oil[i+n][0][0] = oil[i][0][0] = a;
		oil[i+n][0][1] = oil[i][0][1] = b;
		oil[n-i+1][1][0] = oil[2*n-i+1][1][0] = a;
		oil[n-i][1][1] = oil[2*n-i][1][1] = b;
	}
	for(int i = 1;i <= 2*n;i++){//前缀和表示加油-耗油
		for(int j = 0;j <= 1;j++){
			sum[i][j] = sum[i-1][j]+oil[i][j][0]-oil[i][j][1];
		}
	}
	for(int i = 1;i <= 2*n;i++){//单调队列求最小
		for(int j = 0;j <= 1;j++){
			while(q[ans[j]][j].id<=i-n&&len[j]-ans[j]+1){
				ans[j]++;
			}
			while(len[j]-ans[j]+1&&q[len[j]][j].sum>=sum[i][j]){
				len[j]--;
			}
			q[++len[j]][j].sum = sum[i][j];
			q[len[j]][j].id = i;
			minn[i][j] = q[ans[j]][j].sum;
		}
	}
/*	for(int i = 1;i <= 2*n;i++){
		for(int j = 0;j<= 1;j++){
			printf("%d ",sum[i][j]);
		}
		printf("\n");
	}
	for(int i = 1;i <= 2*n;i++){
		for(int j = 0;j <= 1;j++){
			printf("%d ",minn[i][j]);
		}
		printf("\n");
	}*/
	for(int i = 1;i <= n;i++){
		if(minn[i+n-1][0]-sum[i-1][0]>=0||minn[i+n-1][1]-sum[i-1][1]>=0){
			printf("TAK\n");
			continue;
		}
		printf("NTE\n");
	}
	return 0;
}

帮调，本蒟蒻感谢各位大佬！