记录编号	463259	评测结果	AAAAAAAAAA
题目名称	166.[USACO Mar07] 平衡的阵容	最终得分	100
用户昵称	sssSSSay	是否通过	通过
代码语言	C++	运行时间	0.128 s
提交时间	2017-10-23 21:20:47	内存使用	11.87 MiB

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

map <int, int> hs;

const int Maxn = 1010000;

struct node {
	int p, x;	
} a[Maxn];

int n, temp, s[Maxn], ans;

bool comp(node a, node b) {return a.x < b.x;}

int main() {
	freopen("balance.in", "r", stdin);
	freopen("balance.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d%d", &a[i].p, &a[i].x), a[i].x += 1;
	sort(a + 1, a + n + 1, comp);
	for(int i = 1; i <= n; ++i) {
		temp += (a[i].p ? 1 : -1);
		s[i] = temp;
	}
	for(int i = 1; i <= n; ++i) {
//		cout << s[i] << ' ' << a[i].x << ' ' << hs[s[i]] << endl;
		if(hs[s[i]] != 0) ans = max(ans, a[i].x - hs[s[i]]);
		if(hs[s[i]] == 0) hs[s[i]] = a[i + 1].x;
	}
	printf("%d\n", ans);
	return 0;
}