oj.uz

Submission #1120

# Submission time Handle Problem Language Result Execution time Memory
1120 2013-06-26T06:21:20 Z jiws829 공장 (KOI13_factory) C++
9.4 / 20
 257 ms 12604 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12604 KB Output is correct
2 Correct 0 ms 12604 KB Output is correct
3 Correct 0 ms 12604 KB Output is correct
4 Correct 0 ms 12604 KB Output is correct
5 Correct 0 ms 12604 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12604 KB Output is correct
2 Correct 1 ms 12604 KB Output is correct
3 Correct 4 ms 12604 KB Output is correct

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12604 KB Output is correct
2 Correct 26 ms 12604 KB Output is correct
3 Correct 41 ms 12604 KB Output is correct

Subtask #4
0.0 / 4.8

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 12604 KB Output isn't correct
2 Halted 0 ms 0 KB -
3 Halted 0 ms 0 KB -
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 5.8

# Verdict Execution time Memory Grader output
1 Incorrect 257 ms 12604 KB Output isn't correct
2 Halted 0 ms 0 KB -
3 Halted 0 ms 0 KB -
4 Halted 0 ms 0 KB -
5 Halted 0 ms 0 KB -
6 Halted 0 ms 0 KB -