2306: Marriage
ResultTIME LimitMEMORY LimitRun TimesAC TimesJUDGE3s8192K50373Standard
Now, a lot of persons holding their marriages together are in fashion. One day, a lot of people hold their marriages together. They are all happy, so they want to play a game. They stand in two lines, one faces one. The men are in one line, the women are in another. They stand arbitrarily. Then, there will be some red lines to link each couple. So can you calculate how many pairs of the red lines are overlaped.
Input
There are several cases in the input, each case begin with a postive integer N(N<=300000), which means there are N couples, 0 means the end of the file. The following 2 lines each consists of N integers. Each integer represents a couple. The first line are men, the second are women.
Output
For each case output how many pairs of lines are overlaped.
Sample Input
3
1 2 3
3 2 1
3
1 2 3
1 2 3
0
Sample Output
3
0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000+100;
int a[maxn],t[maxn];
long long cnt;
void merge_sort(int x,int y)
{
if(y-x>1)
{
int m=x+(y-x)/2;
int p=x,q=m,i=x;
merge_sort(x,m);
merge_sort(m,y);
while(p<m||q<y)
{
if(q>=y||(p<m&&a[p]<=a[q])) t[i++]=a[p++];
else {t[i++]=a[q++];cnt+=m-p;}
}
for(i=x;i<y;i++) a[i]=t[i];
}
}
int sa[maxn],rank[maxn];
int main()
{
int n;
while(scanf("%d",&n)==1&&n)
{
// memset(a,0,sizeof(a));
// memset(t,0,sizeof(t));
// for(int i=0;i<n;i++) cin>>a[i];
// cnt=0;
// merge_sort(0,n);
for(int i=0;i<n;i++)
{
scanf("%d",&sa[i]);
rank[sa[i]]=i;
}
for(int i=0;i<n;i++)
{
int x;scanf("%d",&x);
a[i]=rank[x];
}
cnt=0;
merge_sort(0,n);
cout<<cnt<<endl;
}
return 0;
}
