POJ 3067 Japan

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lowbit(x) (x)&(-x)
#define ll long long
using namespace std;

struct Road{
    int w, e;
    bool operator < (const Road& b)const
    {
        if(w != b.w) return w<b.w;
        return e<b.e;
    }
}r[1000005];

int c[1005];
int n, m, k;

void add(int x, int val)
{
    for(int i = x; i <= 1000; i += lowbit(i))
        c[i] += val;
}

int sum(int x)
{
    int ret = 0;
    for(int i = x; i > 0; i -= lowbit(i))
            ret += c[i];
    return ret;
}

void solve()
{
    memset(c, 0, sizeof(c));
    sort(r, r+k);
    ll res = 0;
    for(int i = 0; i < k; ++i){
        res += i-sum(r[i].e);
        add(r[i].e, 1);
    }
    printf("%I64d\n", res);
}

int main()
{
    int t, cn = 0;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 0; i < k; ++i)
            scanf("%d%d", &r[i].w, &r[i].e);
        printf("Test case %d: ", ++cn);
        solve();
    }
    return 0;
}