제출 #678006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678006		buidangnguyen05	Ekoeko (COCI21_ekoeko)	C++14	110 / 110	14 ms	3968 KiB

Main

//source: 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5 + 10, M = 26;
int a[N], cnt[M];
queue<int> pos[M];

struct BinaryIndexedTree {
	int bit[N];

	void up(int x, int val) {
		while (x) {
			bit[x] += val;
			x -= x & (-x);
		}
	}

	int get(int x) {
		int ret = 0;
		while (x < N) {
			ret += bit[x];
			x += x & (-x);
		}
		return ret;
	}
} bit;

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	#ifdef LOCAL_MACHINE 
		if (fopen("task.inp", "r")) {
			freopen("task.inp", "r", stdin);
			freopen("task.out", "w", stdout);
		}
	#endif
	
	int n; cin >> n;
	string s; cin >> s;
	for (int i = 0; i < 2 * n; ++i) ++cnt[a[i] = s[i] - 'a'];

	for (int i = 0; i < M; ++i) cnt[i] /= 2;

	vector<int> b;
	for (int i = 0; i < 2 * n; ++i) if (cnt[a[i]]) {
		b.push_back(a[i]);
		--cnt[a[i]];
	}

	for (int i = 0; i < n; ++i) b.push_back(b[i]);
	for (int i = 0; i < 2 * n; ++i) pos[b[i]].push(i + 1);

	ll res = 0;
	for (int i = 0; i < 2 * n; ++i) {
		int x = pos[a[i]].front(); pos[a[i]].pop();
		res += bit.get(x); bit.up(x, 1);
	}

	cout << res << "\n";
}

// ඞඞඞඞඞ you sus

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