BZOJ3314 [Usaco2013 Nov]Crowded Cows

又搬blog。发现这里可以自定义css之后就果断了。

写道水题试试。set的应用。然后还写丑WA了两次，我没救了。

代码高亮是坏了吗？不要吓我。

决定直接用oj7的代码版了，没有高亮就算了。

#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

typedef multiset <int> rb_tree;
typedef rb_tree :: iterator rb_node;
typedef pair <int, int> cow;

const int maxn = 50009;

int n, d, x[maxn], a[maxn], r[maxn];
cow c[maxn];
rb_tree t;

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d", &n, &d);
	for (int i = 1; i <= n; ++ i) {
		scanf("%d%d", x + i, a + i);
		c[i] = cow(x[i], a[i]);
		r[i] = 0;
	}
	sort(c + 1, c + n + 1);
	for (int i = 1; i <= n; ++ i) {
		x[i] = c[i]. first;
		a[i] = c[i]. second;
	}
	for (int i = 1, j = 1; i <= n; ++ i) {
		while (x[i] - x[j] > d) {
			t. erase(t. find(a[j]));
			++ j;
		}
		if (t. lower_bound(a[i] << 1) != t. end())
			++ r[i];
		t. insert(a[i]);
	}
	t. clear();
	int ans(0);
	for (int i = n, j = n; i; -- i) {
		while (x[j] - x[i] > d) {
			t. erase(t. find(a[j]));
			-- j;
		}
		if (t. lower_bound(a[i] << 1) != t. end())
			++ r[i];
		if (r[i] == 2)
			++ ans;
		t. insert(a[i]);
	}
	printf("%d\n", ans);
}