oj.uz

Submission #1394

# Submission time Handle Problem Language Result Execution time Memory
1394 2013-07-03T09:47:11 Z gijun0102 공장 (KOI13_factory) C++
20 / 20
 356 ms 12608 KB 
#include <cstdio>

int tree[2000000],base,index[1001000];

int sum(int l,int r){
	int tmp=0;
	while(l<r){
		if(l%2==1) tmp+=tree[l++];
		if(r%2==0) tmp+=tree[r--];
		l>>=1,r>>=1;
	}
	if(l==r) tmp+=tree[l];
	return tmp;
}
void add(int index){
	while(index){
		tree[index]++;
		index>>=1;
	}
}

int main(){
	int n,i,tmp;
	long long ans=0;
	scanf("%d",&n);
	for(base=1;base<n;base*=2);
	for(i=1;i<=n;i++){
		scanf("%d",&tmp);
		index[tmp]=i;
	}
	for(i=0;i<n;i++){
		scanf("%d",&tmp);
		tmp=index[tmp];
		ans+=sum(tmp+1+base,n+base);
		add(tmp+base);
	}
	printf("%lld",ans);
}

Subtask #1
2.2 / 2.2

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

Subtask #2
3.4 / 3.4

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

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12608 KB Output is correct
2 Correct 30 ms 12608 KB Output is correct
3 Correct 41 ms 12608 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 57 ms 12608 KB Output is correct
2 Correct 101 ms 12608 KB Output is correct
3 Correct 123 ms 12608 KB Output is correct
4 Correct 202 ms 12608 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 271 ms 12608 KB Output is correct
2 Correct 295 ms 12608 KB Output is correct
3 Correct 291 ms 12608 KB Output is correct
4 Correct 346 ms 12608 KB Output is correct
5 Correct 338 ms 12608 KB Output is correct
6 Correct 356 ms 12608 KB Output is correct