MSE06H - Japan

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<algorithm>
#define MAX   1010
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
ll t[MAX];
ii b[MAX*MAX];
int m,n,k;
int nt,c;
bool cmp(const ii &a,const ii &b) {
    if (a.first>b.first) return (true);
    if (a.first<b.first) return (false);
    return (a.second>b.second);
}
void init(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%d",&k);
    int i;
    for (i=1;i<=k;i=i+1) {
        scanf("%d",&b[i].first);
        scanf("%d",&b[i].second);
    }
    for (i=1;i<=m;i=i+1) t[i]=0;
    sort(&b[1],&b[k+1],cmp);
}
void update(int i) {
    while (1<=i && i<=m) {
        t[i]++;
        i=i+(i&(-i));
    }
}
ll sum(int i) {
    ll res=0;
    while (1<=i && i<=m) {
        res=res+t[i];
        i=i&(i-1);
    }
    return (res);
}
void process(void) {
    int i;
    ll res=0;
    for (i=1;i<=k;i=i+1) {
        update(b[i].second);
        res=res+sum(b[i].second-1);
    }
    printf("Test case %d: %lld\n",c,res);
}
int main(void) {
    scanf("%d",&nt);
    for (c=1;c<=nt;c=c+1) {
        init();
        process();
    }
    return 0;
}

Download