Submission #1163544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163544		Ruichen	Ekoeko (COCI21_ekoeko)	C++20	110 / 110	34 ms	14668 KiB

Main

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

struct node{
	int S, E, M, val=1;
	node *left, *right;
	node(int s, int e): S(s), E(e){
		if(S==E){
			val=1;
			return;
		}
		M=S+(E-S)/2;
		left=new node(S,M);
		right=new node(M+1,E);
		val=left->val+right->val;
	}
	void upd(int m, int x){
		if(S==E){
			val=x;
			return;
		}
		if(m<=M){
			left->upd(m,x);
		}
		else{
			right->upd(m,x);
		}
		val=left->val+right->val;
	}
	int qry(int l, int r){
		if(S>r||E<l){
			return 0;
		}
		if(l<=S&&E<=r){
			return val;
		}
		return left->qry(l,r)+right->qry(l,r);
	}
}*segtree;

signed main(){
	int n, ans=0;
	cin >> n;
	string s;
	cin >> s;
	segtree = new node(0,n-1);
	//cout << s << " " << s[0]-'a' << endl;
	vector<int> a(26,0), c(26,0);
	for(int i=0; i<n; i++){
		a[s[i]-'a']++;
		a[s[n+i]-'a']++;
		c[s[i]-'a']++;
	}
	string ms1="", ms2="", fs1="", fs2="";
	int p=0;
	for(int i=n-1; i>=0; i--){
		if(c[s[i]-'a']>a[s[i]-'a']/2){
			c[s[i]-'a']--;
			ans+=n-i-1-p;
			p++;
			ms1+=s[i];
		}
		else{
			fs1+=s[i];
		}
	}
	p=0;
	for(int i=n; i<n*2; i++){
		if(c[s[i]-'a']<a[s[i]-'a']/2){
			c[s[i]-'a']++;
			ans+=i-n-p;
			p++;
			ms2+=s[i];
		}
		else{
			fs2+=s[i];
		}
	}
	ans+=p*p;
	//cout  << fs1 << " " << fs2 << " " << ms1  << " " << ms2 << endl;
	stack<char> t;
	for(int i=0; i<(long long)fs1.length(); i++){
		t.push(fs1[i]);
	}
	for(int i=0; i<(long long)fs1.length(); i++){
		fs1[i]=t.top();
		t.pop();
	}
	for(int i=0; i<(long long)ms1.length(); i++){
		t.push(ms1[i]);
	}
	for(int i=0; i<(long long)ms1.length(); i++){
		ms1[i]=t.top();
		t.pop();
	}
	fs1=fs1+ms2;
	fs2=ms1+fs2;
	//3cout << fs1 << " " << fs2 << endl;
	vector<vector<int> >fn(26);
	vector<int> in(26,0);
	for(int i=0; i<(long long)fs2.length(); i++){
		fn[fs2[i]-'a'].push_back(i);
	}
	for(int i=0; i<(long long)fs1.length(); i++){
		//cout << fn[fs1[i]-'a'][in[fs1[i]-'a']] << endl;
		//cout << segtree->qry(0,0) << endl;
		ans+=segtree->qry(0,fn[fs1[i]-'a'][in[fs1[i]-'a']]-1);
		//cout << ans << endl;
		segtree->upd(fn[fs1[i]-'a'][in[fs1[i]-'a']],0);
		in[fs1[i]-'a']++;
	}
	cout << ans << endl;
}

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