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;
}