SPOJ MSE06H - Japan

MSE06H.cpp

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define endl '\n'
#define PB push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef pair<int, char> ic;

const int oo = ~(1<<31);

struct fenwick_tree {
    int n; vll data;
    fenwick_tree(int _n) : n(_n), data(vll(n)) { }
    void update(int at, int by) {
        while (at < n) data[at] += by, at |= at + 1;
    }
    ll query(int at) {
        ll res = 0LL;
        while (at >= 0)
            res += data[at], at = (at & (at + 1)) - 1;
        return res;
    }
    ll rsq(int a, int b) {
        return query(b) - query(a - 1);
    }
};

int main() {

    #ifndef CBDAVIDES
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    #endif

    int t, m, n, k, z = 1;

    cin >> t;
    while(t--) {
        cin >> n >> m >> k;

        vii A(k);
        for(ii &i : A)
            cin >> i.F >> i.S;

        sort(A.begin(), A.end());
        fenwick_tree N(1005), M(1005);

        ll cont = 0;
        for(ii p : A) {

            cont += min(
                N.rsq(0, max(p.F - 1, 0)),
                M.rsq(min(1001 , p.S + 1), 1001)
            );

            N.update(p.F, 1);
            M.update(p.S, 1);

        }

        cout << "Test case " << z++ << ": ";
        cout << cont << endl;
    }

    return 0;
}