spoj/YODANESS.cpp at master · prateekchandan/spoj · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <tr1/unordered_map>
using namespace std;
int county;

void merge(vector<int> a,int st,int en,int i1,int j1,vector<int> &n){

	for (int i = st; i <= j1; i++)
	{
		if(st>en)
		{
			n[i]=a[i1];
			i1++;
			county+=en-st+1;

		}
		else if(i1>j1)
		{
			n[i]=a[st];
			st++;
		}
		else if(a[st]<a[i1])
		{
			n[i]=a[st];
			st++;
		}
		else{
			n[i]=a[i1];
			i1++;
			county+=en-st+1;

		}
	}

}
void mergesort(vector<int> &n,int st,int en){

	if(st >= en)
		return;

	int mid=(st+en)/2;
	mergesort(n,st,mid);
	mergesort(n,mid+1,en);
	merge(n,st,mid,mid+1,en,n);

	/*cout<<"\n************************\n";
		cout<<st<<":"<<mid<<":"<<en<<" & "<<county<<endl;
		for (int i = st; i <= mid; i++)
		{
			cout<<n[i]<<" ";
		}
		cout<<endl;
		for (int i = mid+1; i <= en; i++)
		{
			cout<<n[i]<<" ";
		}

		cout<<endl;
		for (int i = st; i <= en; i++)
		{
			cout<<n[i]<<" ";
		}

	cout<<"\n************************\n";*/


}
int main(){
	int t,n;
	string a;
	cin>>t;
	while (t--)
	{
		county=0;
		cin>>n;

		tr1::unordered_map<string,int> x;
		vector<int> z(n);

		for (int i = 0; i < n; i++)
		{
			cin>>a;
			x[a]=i;
		}

		for (int i = 0; i < n; i++)
		{
			cin>>a;
			z[i]=x[a];
			//cout<<z[i]<<" : "  ;
		}
		//cout<<endl;

		mergesort(z,0,n-1);

		cout<<county<<endl;
	}

	return 0;
}