4226. Japan

japan.cpp

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define blen 1005
using namespace std;
 
long long int ac[blen];

void update(int ix, int val, int n){
	int nv = val;
	for(; ix <= n; ix += (ix & -ix))
		ac[ix] += val;
}
 
long long int query(int ix){
	long long int r = 0;
	while(ix){
		r += ac[ix];
		ix -= (ix & -ix);
	}
	return r;
}
 
struct bridge{
	int E;
	int W;
};
 
inline bool operator<(const bridge& a, const bridge& b)
{
	return (a.E == b.E) ? a.W < b.W : a.E < b.E;
}
 
int main(){
	cin.sync_with_stdio(false);
	int T;
	int N, M, e, w, mw = 0;
	long long int K;
	cin >> T;
	T++;
	for(int ix = 1; ix < T; ix++) { 
		cin >> N >> M >> K;
		int n = K;
		vector<bridge> bridges;
		long long int res = 0;
		memset(ac, 0, sizeof(long long int)*(blen)); 
		while(K--){
			cin >> e >> w;
			bridge b;
			b.E = e;
			b.W = w;
			mw = (w > mw) ? w : mw;	
			bridges.push_back(b);
		}
		std::sort (bridges.begin(), bridges.end()); 
		for(int i = 0; i < n; i++){
			update(bridges[i].W,1, mw);
		}
		for(int i = 0; i < n; i++){
			long long int q = query(bridges[i].W - 1);
			res += q; 
			update(bridges[i].W,-1, mw);
		}
		
		cout << "Test case " << ix << ": " << res << endl;
	}
	return 0;
}