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