MSE06H - Japan

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long LL;
#define fi first
#define se second
#define M 1000
#define TR(v, it) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

int bit[M+1], n, m, k;

bool cmp(const ii&a, const ii&b) {
	return a.fi < b.fi || a.fi == b.fi && a.se > b.se;
}

void add(int i, int v) {
	for(; i <= m; i += i & -i) bit[i] += v;
}

LL sum(int i) {
	LL res = 0;
	for(; i > 0; i -= i & -i) res += bit[i];
	return res;
}

int main() {
	int tc; scanf("%d", &tc);
	for(int test = 1; test <= tc; ++test) {
		vii hw; //highway
		scanf("%d%d%d", &n, &m, &k);
		for(int i = 0; i < k; ++i) {
			int x, y; scanf("%d%d", &x, &y);
			hw.push_back(ii(x, m-y+1));
		}
		sort(hw.begin(), hw.end(), cmp);
		memset(bit, 0, sizeof bit);
		LL res = 0;
		TR(hw, it) {
			res += sum(it->se - 1);
			add(it->se, 1);
		}
		printf("Test case %d: %lld\n", test, res);
	}
	return 0;
}

Download