2238126_ac_93ms_1196k.cpp

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <algorithm>
# define MAX 60001

long a[MAX], b[MAX], c[MAX], d[MAX];
int st[MAX];
long cnt;

bool cmp(int i,int j)
{
	return b[i] < b[j];
}

void MergeSort(int l,int r)
{
      int mid,i,j,tmp;

      if (r>l+1)
      {
          mid = (l+r)/2;
          MergeSort(l,mid);
          MergeSort(mid,r);
          tmp = l;
          for (i=l,j=mid;i<mid&&j<r;)
          {
              if (a[i]>=a[j])
              {
                  c[tmp++] = a[j++];
                  cnt+=mid-i;
              }
              else   c[tmp++] = a[i++];
          }
	if (j<r)
		for (;j<r;++j) c[tmp++] = a[j];
        else
		for (;i<mid;++i)   c[tmp++] = a[i];
	for (i = l ; i < r; ++i)
              a[i] = c[i];
      }
}

void input()
{
	int n, m, i;

	cnt = 0;
	scanf("%d%d",&n,&m);
	for(i = 0; i < n+m; i++)
		scanf("%ld%ld",&b[i],&d[i]);
	for(i = 0; i < m+n; i++)
		st[i] = i;
	std::sort(st,st+m+n,cmp);
	for(i = 0; i < n+m; i++)
		a[i] = d[st[i]];
	MergeSort(0,m+n);
	printf("%ld\n\n",cnt);
}

int main()
{
	int i, t;

	scanf("%d",&t);
	for(i = 1; i <= t; i++)
	{
		printf("Scenario #%d:\n",i);
		input();
	}
	return 1;
}