Submission #1003932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003932		vjudge1	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	14 ms	6496 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
array<int, MAXN> bit;

void update(int id, int val)
{
	while (id < MAXN)
	{
		bit[id] += val;
		id += id&-id;
	}
}

int query(int id)
{
	int resp = 0;
	while (id > 0)
	{
		resp += bit[id];
		id -= id&-id;
	}
	return resp;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	string s;
	cin >> s;
	vector<vector<int>> freq(30);
	for (int i = 0; i < 2*N; i++) freq[s[i]-'a'].push_back(i);
	vector<int> v1(2*N);
	vector<pair<int, int>> pares;
	for (int c = 0; c < 30; c++)
	{
		int sz = freq[c].size();
		for (int i = 0; i < sz/2; i++) 
		{
			v1[freq[c][i]] = 0; v1[freq[c][i+sz/2]] = 1;
			pares.emplace_back(freq[c][i], freq[c][i+sz/2]);
		}
	}
	int resp = 0, cnt1 = 0;
	for (int i = 0; i < 2*N; i++)
	{
		if (v1[i]) cnt1++;
		else resp += cnt1;
	}

	sort(pares.rbegin(), pares.rend());
	for (auto &[x, y] : pares)
	{
		++y;
		resp += query(y);
		update(y, +1);
	}
	cout << resp << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40