Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

尼玛!一道逆序数纠结我好几天,终于AC,庆祝一下,靠!!!

Posted by hncu110640108 at 2012-11-22 21:16:58 on Problem 2481
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,b[100010],c[100010];
int nima;
struct node{
	int t1;
	int t2;
	int num;
}a[100010];
bool cmp(struct node a,struct node b)
{
	if(a.t1==b.t1)
		return a.t2<b.t2;
	return a.t1>b.t1;
}
int lowbit(int x)
{
	return x&(-x);
}
void insert(int x)
{
	while(x<=nima)
	{
		c[x]+=1;
		x=x+lowbit(x);
	}
}
int sum(int x,int y)
{
	int s=0;
	while(y>=x)
	{
		s+=c[y];
		y=y-lowbit(y);
	}
	return s;
}
int main()
{
   int i,j;
   while(scanf("%d",&n)!=EOF&&n)
   {
	   nima=-1;
	   for(i=1;i<=n;i++)
	   {
		   scanf("%d%d",&a[i].t1,&a[i].t2);
		   a[i].num=i;
		   if(nima<a[i].t2)
			   nima=a[i].t2;
	   }
	   memset(c,0,sizeof(c));
       sort(a+1,a+n+1,cmp);
	   /*for(i=1;i<=n;i++)
		   printf("%d %d\n",a[i].t1,a[i].t2);*/
	   b[a[n].num]=sum(a[n].t2,nima)-sum(1,a[n].t2-1);
	   insert(a[n].t2);
	   for(j=1,i=n-1;i>=1;i--,j++)
	   {
		   if(a[i].t1!=a[i+1].t1||a[i].t2!=a[i+1].t2)
		      b[a[i].num]=j-sum(1,a[i].t2-1);
		   else
			  b[a[i].num]=b[a[i+1].num];
		   insert(a[i].t2);	 
	   }
	 /*  for(i=1;i<=n;i++)
		   printf("%d ",c[i]);
	   printf("\n");*/
      for(i=1;i<n;i++)
			printf("%d ",b[i]);
		printf("%d\n",b[n]);
   }
   return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator