BZOJ3888 [Usaco2015 Jan]Stampede

usaco的银组都开始考这种题了么。其实还是挺水的，不过题号比较好。

就按y排序，挨个把时间轴上的东西扔掉就完了。写离散可能还没有直接写smt快呢。

然后线段有一边要减1有点坑。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long dint;
#define _l (long long int)

struct cow {
	int y;
	int ta, tb;
};

struct node {
	int l, r, w;
	node *ls, *rs;
};
typedef pair <node*, node* > npr;

const int maxn = 50009;

inline bool operator <(const cow& a, const cow& b) {
	return a. y < b. y;
}

int n, ans;
cow a[maxn];
node nlst[maxn << 1], *np(nlst), *rt;

node* newNode(int l, int r) {
	np-> l = l;
	np-> r = r;
#ifdef WIN32
	np-> w = (rand() << 16) | rand();
#else
	np-> w = rand();
#endif
	np-> ls = np-> rs = 0;
	return np ++;
}

npr split(node* p, int x) {
	if (!p)
		return npr(0, 0);
	else if (x < p-> l) {
		npr g(split(p-> ls, x));
		p-> ls = g. second;
		return npr(g. first, p);
	}
	else if (x >= p-> r) {
		npr g(split(p-> rs, x));
		p-> rs = g. first;
		return npr(p, g. second);
	}
	else {
		node *q(newNode(p-> l, x));
		q-> ls = p-> ls;
		p-> ls = 0;
		p-> l = x + 1;
		return npr(q, p);
	}
}
node *merge(node* p, node* q) {
	if (!p)
		return q;
	else if (!q)
		return p;
	else if (p-> w > q-> w) {
		p-> rs = merge(p-> rs, q);
		return p;
	}
	else {
		q-> ls = merge(p, q-> ls);
		return q;
	}
}

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

	srand(239473);
	scanf("%d", &n);
	for (int i = 0; i < n; ++ i) {
		int x, r;
		scanf("%d%d%d", &x, &a[i]. y, &r);
		a[i]. ta = - x * r - r + 1;
		a[i]. tb = - x * r;
	}
	rt = newNode(-1, 1000000009);
	ans = 0;
	sort(a, a + n);
	for (int i = 0; i < n; ++ i) {
		npr x(split(rt, a[i]. ta - 1));
		npr y(split(x. second, a[i]. tb));
		if (y. first)
			++ ans;
		rt = merge(x. first, y. second);
	}
	printf("%d\n", ans);
}