Submission #33456454

---

Source Code Expand

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int MN=3e5+5;
int n,col[MN],val[MN];

vector<int>vec[MN];

struct BIT{
	int c[MN];
	int lowbit(int x){return x&(-x);}
	void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i))c[i]+=k;}
	int sum(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
	void clear(){memset(c,0,sizeof(c));}
}T;

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	n=read();int ans=0;
	for(int i=1;i<=n;i++)col[i]=read();
	for(int i=1;i<=n;i++)val[i]=read();
	for(int i=1;i<=n;i++){
		ans+=T.sum(n)-T.sum(val[i]);
		T.add(val[i],1);
	}
	for(int i=1;i<=n;i++)T.add(val[i],-1);
	for(int i=1;i<=n;i++)vec[col[i]].push_back(val[i]);
	for(int i=1;i<=n;i++){
		for(int p:vec[i]){
			ans-=T.sum(n)-T.sum(p);
			T.add(p,1);
		}
		for(int p:vec[i])T.add(p,-1);
	}
	cout<<ans<<endl;

	return 0;
}

Submission Info

Judge Result