Submission #1394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1394		gijun0102	공장 (KOI13_factory)	C++98	20 / 20	356 ms	12608 KiB

factory

#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
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 4.8 / 4.8
• Subtask 5: 5.8 / 5.8