Submission #1003838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003838		vjudge1	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	42 ms	13524 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 200010;

vector <int> c[26];

struct Segtree{
	int tree[4*N];
	Segtree(){
		for(int i = 0;i < 4*N;i++) tree[i] = 0;
	}
	int join(int a, int b){
		return a+b;
	}
	void update(int node, int l, int r, int pos, int val){
		if(l == r){
			tree[node] += val;
			return;
		}
		int mid=  (l+r)/2;
		if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
		else update(2*node+1, mid+1, r, pos, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		if(l > tr or tl > r) return 0;
		if(l <= tl and tr <= r) return tree[node];
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl , mid), query(2*node+1, l, r, mid+1, tr));
	}
}seg;

vector <int> srt;
int tam[26];

int32_t main(){
	int n;
	cin>> n;
	string s;
	cin >> s;
	vector <int> v1, v2;
	for(int i = 0;i < 2*n;i++){
		c[s[i]-'a'].push_back(i+1);
	}
	for(int i = 0;i < 26;i++){
		tam[i] = c[i].size();
		tam[i] /= 2;
		tam[i]--;
	}
	for(int i = 2*n;i > 0;i--){
		if(tam[s[i-1]-'a'] < 0) continue;
		c[s[i-1]-'a'].pop_back();
		v2.push_back(i);
		v1.push_back(c[s[i-1]-'a'][tam[s[i-1]-'a']]);
		tam[s[i-1]-'a']--;
	}
	reverse(v1.begin(), v1.end());
	reverse(v2.begin(), v2.end());
	for(auto x : v1) srt.push_back(x);
	for(auto x : v2) srt.push_back(x);
	int res = 0;
	for(auto x : srt){
		//cout << x << ' ';
		res += seg.query(1,x, 2*n, 1, 2*n);
		seg.update(1, 1, 2*n, x, 1);
	}
	cout << res << endl;
	return 0;
}

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