比赛 20161215 评测结果 AAWWWWWWWWWWWWW
题目名称 奔跑 最终得分 13
用户昵称 KZNS 运行时间 0.726 s
代码语言 C++ 内存使用 1.64 MiB
提交时间 2016-12-16 21:29:17
显示代码纯文本
//KZNS
#include <cstdio>
#include <algorithm>
#include <map>
#include <utility>
using namespace std;
#define Nmax 50003
typedef pair<int, pair<int, int> > poi;
int N;
poi Pls[Nmax];
int Tls[Nmax * 2];
int T;
map<int, int> mp;
int FFF[Nmax * 2];
int ans = 0;
int main() {
	freopen("stampede.in", "r", stdin);
	freopen("stampede.out", "w", stdout);
	scanf("%d", &N);
	int a, b, c;
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d", &a, &b, &c);
		Pls[i] = make_pair(b, make_pair((-a-1)*c, (-a)*c));
		Tls[i<<1] = (-a-1)*c;
		Tls[i<<1^1] = (-a)*c;
	}
	sort(Tls, Tls+N*2);
	mp[Tls[0]] = 1;
	T = 1;
	for (int i = 1; i < (N<<1); i++) {
		if (Tls[i] != Tls[i-1])
			mp[Tls[i]] = ++T;
	}
	sort(Pls, Pls+N);
	pair<int, int> u;
	bool f;
	int hhh;
	for (int i = 0; i < N; i++) {
		u = Pls[i].second;
		f = false;
		hhh = mp[u.second];
		for (int j = mp[u.first]; j <= hhh; j++) {
			if (FFF[j])
				j = FFF[j];
			else {
				f = true;
				FFF[j] = hhh;
			}
		}
		if (f)
			ans++;
	}
	printf("%d\n", ans);
	return 0;
}
//UBWH