Submission #1120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120		jiws829	공장 (KOI13_factory)	C++98	9.40 / 20	257 ms	12604 KiB

factory

#include<stdio.h>
int p[500001],t[1000001],q[500001];
int bi[1000001];
int n;
int sum;
int fin(int a,int b)
{
	while(1)
	{
		if(a>b) break;
		if(a%2==1)
		{
			sum+=bi[a];
			a++;
		}
		if(b%2==0)
		{
			sum+=bi[b];
			b--;
		}
		a/=2;
		b/=2;		
	}
}
int main()
{
	scanf("%d",&n);
	int i,j;
	
	int a;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		t[a]=i;
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		q[i]=t[a];
	}
	for(i=1;i<=n;i++)
	{
		p[q[i]]=i;
	}
	//for(i=1;i<=n;i++) printf("%d ",p[i]);
	
	int m=1,now;
	while(1)
	{
		if(m>n) break;
		m*=2;		
	}
	//printf("%d\n",m);
	
	for(i=1;i<=n;i++)
	{
		fin(m+p[i]-1,m+n-1);
		//printf("%d %d  %d\n",m+p[i]-1,m+n-1,sum);
		
		now=m+p[i]-1;
		while(1)
		{
			bi[now]++;
			now/=2;
			if(now==0) break;
		}
	}
	printf("%d",sum);
}

• Subtask 1: 2.2 / 2.2
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 0 / 4.8
• Subtask 5: 0 / 5.8