奥赛一本通 旅行问题

// 旅行问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <deque>
#include <cstring>
using namespace std;

/*
http://ybt.ssoier.cn:8088/problem_show.php?pid=1600

原题来自：POI 2004

John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 n
 车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。
 John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。
 在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上
 （起点站亦是如此），行驶过程中不能出现没有油的情况。

任务：判断以每个车站为起点能否按条件成功周游一周。

【输入】
第一行是一个整数 n，表示环形公路上的车站数；

接下来 n行，每行两个整数 pi,di，
 分别表示表示第 i号车站的存油量和第 i号车站到下一站的距离。

【输出】
输出共 n行，如果从第 i 号车站出发，一直按顺时针（或逆时针）方向行驶，
能够成功周游一圈，则在第 i行输出 TAK，否则输出 NIE。

【输入样例】
5
3 1
1 2
5 2
0 1
5 4


【输出样例】
TAK
NIE
TAK
NIE
TAK



//======================================
10
10 1
5 0
14 7
18 9
7 6
0 3
6 8
17 3
18 9
19 7

TAK
TAK
TAK
TAK
NIE
NIE
NIE
TAK
TAK
TAK
//========================
10
5 6
6 1
12 7
10 2
14 1
9 9
10 1
12 2
15 3
3 1

TAK
TAK
TAK
TAK
TAK
TAK
TAK
TAK
TAK
TAK


数据范围与提示：

对于全部数据，3≤n≤10^6,0≤pi≤2×10^9,0<di≤2×10^9。
*/
int n;
const int N = 3000010;
long long a[N];
int p[N], d[N];

//long long pre[N];
int ans1[N];
int ans2[N];


void solve1() {
	memset(ans1, -1, sizeof ans1);
	memset(a, 0, sizeof a);
	for (int i = 1; i <= n; i++) {
		a[i] = p[i] - d[i];
	}
	//化环成链
	memcpy(&a[n + 1], &a[1], sizeof(a[0]) * n);
	for (int i = 1; i <= n + n; i++) {
		a[i] += a[i - 1];
	}
	deque<int> q;
	for (int i = 2 * n; i >= 0; i--) {
		while (!q.empty() && q.front() - i > n ) q.pop_front();
		while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
		if (i < n) {
			if (!q.empty() && a[q.front()] < a[i]) {
				ans1[i+1] = q.front();
			}
		}
		q.push_back(i);
	}

}


void solve2() {
	memset(ans2, -1, sizeof ans2);
	memset(a, 0, sizeof a);
	d[0] = d[n];
	for (int i = n; i >= 1; i--) {
		a[n-i+1] = p[i] - d[i - 1];
	}
	//化环成链
	memcpy(&a[n + 1], &a[1], sizeof(a[0]) * n);
	for (int i = 1; i <= n + n; i++) {
		a[i] += a[i - 1];
	}

	deque<int> q;
	for (int i = 2 * n; i >= 0; i--) {
		while (!q.empty() && q.front() - i > n) q.pop_front();
		while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
		if (i < n) {
			int realid = n - i;
			if (!q.empty() && a[q.front()] < a[i]) {
				//ans1[i + 1] = q.front();
				if (ans1[realid] != -1) {
					//cout << "NIE" << endl;
					printf("NIE\n");
				}
				else {
					//cout << "TAK" << endl;
					printf("TAK\n");
				}
			}
			else {
				//cout << "TAK" << endl;
				printf("TAK\n");
			}
		}
		q.push_back(i);
	}

}


int main()
{
	/*ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);*/
	//cin >> n;
	scanf("%d",&n);
	for (int i = 1; i <= n; i++) {
		//cin >> p[i] >> d[i];
		scanf("%d%d", &p[i], &d[i]);
	}
	
	solve1();
	solve2();
	
	return 0;
}