제출 #1163440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163440		siewjh	Ekoeko (COCI21_ekoeko)	C++20	110 / 110	8 ms	4284 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000005;
ll fw[MAXN];
int n;
void update(int x, ll v){
	while (x <= n){
		fw[x] += v;
		x += (x & (-x));
	}
}
ll query(int x){
	ll ans = 0;
	while (x){
		ans += fw[x];
		x -= (x & (-x));
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	vector<int> pos[26], orig(n << 1);
	for (int i = 0; i < (n << 1); i++){
		char ch; cin >> ch;
		orig[i] = ch - 'a';
		pos[ch - 'a'].push_back(i);
	}
	vector<int> swvl, swvr;
	vector<bool> issw(n << 1, 0);
	for (int i = 0; i < 26; i++){
		int sz = pos[i].size() >> 1;
		for (int j = 0; j < sz; j++)
			if (pos[i][j] >= n){
				swvr.push_back(pos[i][j]);
				issw[pos[i][j]] = 1;
			}
		for (int j = sz; j < (sz << 1); j++)
			if (pos[i][j] < n){
				swvl.push_back(pos[i][j]);
				issw[pos[i][j]] = 1;
			}
	}
	sort(swvl.begin(), swvl.end()); sort(swvr.begin(), swvr.end());
	ll ans = 0, oop = swvl.size();
	for (int i = 0; i < oop; i++) ans += (n - 1 - i) - swvl[oop - 1 - i];
	for (int i = 0; i < oop; i++) ans += swvr[i] - (n + i);
	ans += oop * oop;
	vector<int> vl, vr;
	for (int i = 0; i < n; i++) (issw[i] ? vr : vl).push_back(orig[i]);
	for (int i = n; i < (n << 1); i++) (issw[i] ? vl : vr).push_back(orig[i]);
	deque<int> dq[26];
	for (int i = 0; i < n; i++) dq[vl[i]].push_back(i + 1);
	for (int i = 0; i < n; i++){
		int val = dq[vr[i]].front(); dq[vr[i]].pop_front();
		ans += query(n) - query(val);
		update(val, 1);
	}
	cout << ans;
}

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