Submission #1163462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163462		YSH2020	Ekoeko (COCI21_ekoeko)	C++20	110 / 110	40 ms	16184 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
	int l, r, m;
	int val;
	node *left, *right;
	node(int _l, int _r) {
		l = _l; r = _r; m = (l+r)/2;
		val = 0;
		if (l != r) {
			left = new node(l, m);
			right = new node(m+1, r);
		}
	}
	void upd(int n, int v) {
		if (l == n and r == n) {val = v; return;}
		if (n <= m) left -> upd(n, v);
		else right -> upd(n, v);
		val = left->val+right->val;
	}
	int qry(int s, int e) {
		if (s > e) return 0;
		if (s <= l and r <= e) return val;
		if (e <= m) return left->qry(s, e);
		if (s >= m+1) return right->qry(s, e);
		return left->qry(s, m)+right->qry(m+1, e);
	}
}*root;

signed main() {
	int n; cin >> n;
	char x[2*n]; for (int i = 0; i < 2*n; i++) cin >> x[i];
	int counts[26];
	for (int i = 0; i < 26; i++) counts[i] = 0;
	for (int i = 0; i < 2*n; i++) counts[x[i]-'a']++;
	// preprocessing done. now lets find the first half.
	vector<int> half;
	vector<pair<int,int>> unused;
	int used[26]; for (int i = 0; i < 26; i++) used[i] = 0;
	for (int idx = 0; idx < 2*n; idx++) {
		int cur = x[idx]-'a';
		if (used[cur]*2 == counts[cur]) unused.push_back({idx, cur});
		else {
			half.push_back(cur);
			used[cur]++;
		}
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		ans += i+n-unused[i].first;
	}
	//3rd part headache.
	queue<int> tmp[26];
	for (int i = 0; i < n; i++) {
		tmp[half[i]].push(i);
	}
	int actl_val[n];
	for (int i = 0; i < n; i++) {
		actl_val[i] = tmp[unused[i].second].front()+1;
		tmp[unused[i].second].pop();
	}
	//now count inversions
	root = new node(0, n+20);
	for (int i = 0; i < n; i++) {
		ans += root->qry(actl_val[i]+1, n);
		root->upd(actl_val[i], 1);
	}
	cout << ans;
}

/*
 * Imple note: there are 26 letters of the alphabet.
 * Greedy algorithm:
 * Step 1: Find the first half
 * The current letter will be the same as the one in the second-half.
 * So if it can be there then store it that way
 * else just temporarily skip; do until N elements are achieved in the "first-half".
 * Step 2: Shift elements to second half. That can be done using Math, by keeping track of the locations.
 * Step 3: inversion count! A reminder to bash your head over the repeats, as that is very intersting to implement.
 * /
 * 10
 * aaaaaaaaaabbbbbbbbbb
*/

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