记录编号	358620	评测结果	AAWWWWWWWWWWWWW
题目名称	奔跑	最终得分	13
用户昵称	confoo	是否通过	未通过
代码语言	C++	运行时间	0.412 s
提交时间	2016-12-17 16:22:11	内存使用	9.92 MiB

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define lch (o << 1)
#define rch (o << 1 | 1)
#define fa (o >> 1)
#define file(x) "stampede." #x
typedef long long ll;
const int N = 1e5 + 10;
int n, x[N], y[N], c[N], ls[N], rk[N][2], pos[N], sz, ans;
ll at[N];
bool vis[N];
inline bool cmp(int a, int b) {return at[a] < at[b];}
struct PT{int v, w;}st[N << 2];
std::vector<PT> ss[N];
std::vector<int> tt[N];
inline int up(int o) {
	pos[st[o].v] = o;
	while (fa && st[fa].w > st[o].w) std::swap(st[fa], st[o]), std::swap(pos[st[fa].v], pos[st[o].v]), o = fa;
	return o;
}
inline int down(int o) {
	while (lch <= sz) {
		int ch = lch;
		if (rch <= sz && st[rch].w < st[lch].w) ++ch;
		if (st[ch].w < st[o].w) std::swap(st[o], st[ch]), std::swap(pos[st[ch].v], pos[st[o].v]), o = ch;
		else break;
	}
	return o;
}
inline void insert(PT& pt) {
	st[++sz] = pt;
	up(sz);
}
inline void remove(int v) {
	int t = pos[v];
	std::swap(pos[v], pos[st[sz].v]);
	std::swap(st[sz], st[t]);
	--sz;
	down(t);
}
namespace baoli{
	inline bool cmp2(int a, int b) {return y[a] > y[b];}
	int th[N], co[N];
	void sol() {
		for (int i = 1; i <= n; i++) th[i] = i;
		std::sort(th + 1, th + 1 + n, cmp2);
		for (int k = 1; k <= n; k++) {
			int i = th[k];
			for (int j = rk[i][0]; j <= rk[i][1]; j++) co[j] = i;
		}
		memset(vis, 0, sizeof(vis));
		ans = 0;
		for (int i = 1; i <= n << 1; i++) vis[co[i]] = 1;
		for (int i = 1; i <= n; i++) ans += vis[i];
		printf("%d\n",ans);
		ans = 0;
		memset(vis, 0, sizeof(vis));
	}
}
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &x[i], &y[i], &c[i]);
		at[i*2 - 1] = (-1 - x[i])*1ll*c[i];
	 	at[i*2] = at[i*2 - 1] + 1ll*c[i];
	}
	for (int i = 1; i <= n << 1; i++) ls[i] = i;
	std::sort(ls + 1, ls + 1 + (n << 1), cmp);
	int nt = 0;
	for (int i = 1; i <= n << 1; i++) {
		rk[ls[i] + 1 >> 1][!(ls[i]&1)] = ++nt;
		int b = i;
		while (i + 1 <= n << 1 && at[ls[i + 1]] == at[ls[b]]) ++i, rk[ls[i] + 1>> 1][!(ls[i]&1)] = nt;
	}
	baoli::sol();
	return 0;
	for (int i = 1; i <= n; i++) {
		ss[rk[i][0]].push_back((PT){i, y[i]});
		tt[rk[i][1]].push_back(i);
	}
	for (int i = 1; i <= nt; i++) {
		for (int k = 0; k < ss[i].size(); k++) insert(ss[i][k]);
//		printf("%d : see %d\n", i, st[1].v);
		if (sz) vis[st[1].v] = 1;
		for (int k = 0; k < tt[i].size(); k++) remove(tt[i][k]);
	}
	for (int i = 1; i <= n; i++) ans += vis[i];
	printf("%d\n", ans);
}