POJ 3067 japan

14125 단어
//첫 번째 열에 따라 정렬하면 두 번째 열의 역서수를 구하고, 두 번째 열에 따라 정렬하면 땅 한 열의 역서수를 구한다//
AC 코드:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1500
int n,m,k;
int a[N*N];
struct node
{
    int x,y;
}t[N*N];
int cmp(node p,node q)
{
    if(p.x==q.x)
    {
        return p.y<q.y;
    }
    else
    {
        return p.x<q.x;
    }
}
int lower_bit(int i)
{
    return i&(-i);
}
void add(int i,int v)
{
    while(i<=m)
    {
        a[i]+=v;
        i+=lower_bit(i);
    }
}
int sum(int i)
{
    int s=0;
    while(i>0)
    {
        s+=a[i];
        i-=lower_bit(i);
    }
    return s;
}
int main()
{
    int r,o=1;
    scanf("%d",&r);
    while(r--)
    {
        memset(a,0,sizeof(a));
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=k;i++)
        {
            scanf("%d%d",&t[i].x,&t[i].y);
        }
        sort(t+1,t+k+1,cmp);
        long long cnt=0;
        for(int i=1;i<=k;i++)
        {
            add(t[i].y,1);
            cnt+=i-sum(t[i].y);
        }
        printf("Test case %d: %lld
",o++,cnt); } return 0; }

좋은 웹페이지 즐겨찾기