1650.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1650 on 2006-07-25 at 09:36:00 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 65536;

class TreeArray {
private:
	int lmt, a[N];
	int lowBit(int t) const { return t&(-t); }
public:
	void clear(int ni) { lmt = ni; memset(a, 0, sizeof(a)); }
	void insert(int);
	int sum(int);
	int total(int b, int e) { return sum(e)-sum(b-1); }
};
void TreeArray::insert(int n) {
	for(; n <= lmt; n += lowBit(n)) a[n]++;
}
int TreeArray::sum(int n) {
	int r = 0;
	for(; n > 0; n -= lowBit(n)) r += a[n];
	return r;
}

class Peasant {
public:
	int b, e;
	void make() { scanf("%d %d", &b, &e); }
	bool operator <(const Peasant& p) const { return b < p.b; }
};

int main()
{
	TreeArray ta;
	Peasant p[N];
	int n, m, i, t, T;
	
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		scanf("%d %d", &n, &m); n += m;
		for(i = 0; i < n; i++) p[i].make();
		sort(p, p+n); ta.clear(n);
		int cross = 0;
		for(i = 0; i < n; i++) {
			cross += ta.total(p[i].e, n);
			ta.insert(p[i].e);
		}
		printf("Scenario #%d:\n%d\n\n", t, cross);
	}
	
	return 0;
}