Submission #27836105

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
using namespace std;
vector<pair<int, int>>t;
#define int long long
int dp[61][2];
int val[61][2];
int arr[61];
vector<int>b;
int treeN;
int tree[1 << 22];
int quarry(int l, int r, int L, int R, int idx)
{
	if (l <= L && R <= r)
	{
		return tree[idx];
	}
	if (L > r || R < l)
	{
		return 0;
	}
	return quarry(l, r, L, (L + R) / 2, idx * 2) + quarry(l, r, (L + R) / 2 + 1, R, idx * 2 + 1);
}
void update(int idx, int changevalue)
{
	idx += treeN;
	tree[idx] += changevalue;
	while (idx != 1)
	{
		idx /= 2;
		tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
	}
}
map<int, int>aa;
map<int, int>bb;
signed main()
{
	int N;
	cin >> N;
	for (treeN=1; treeN < N; treeN *= 2);
	int i;
	int ans = 0;
	for (i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		t.push_back({ a,0 });
	}
	for (i = 0; i < N; i++)
	{
		cin >> t[i].second;
		b.push_back(t[i].second);
	}
	sort(t.begin(), t.end());
	sort(b.begin(), b.end());
	
	for (i = 0; i < N;)
	{
		int o = t[i].first;
		int j;
		for (j = i; j < N; j++)
		{
			if (t[j].first != o)
				break;
			int p = lower_bound(b.begin(), b.end(), t[j].second) - b.begin();
			update(p, 1);
		}
		for (j = i; j < N; j++)
		{
			if (t[j].first != o)
				break;
			int p = lower_bound(b.begin(), b.end(), t[j].second) - b.begin();
			ans += quarry(p, N - 1, 0, treeN - 1, 1);
		}
		i = j;
		
	}
	cout << ans;
}

Submission Info

Judge Result