Submission #855937

#	Time	Username	Problem	Language	Result	Execution time	Memory
855937		NotLinux	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	26 ms	10020 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SEGT{
	vector < int > tree;
	int sz;
	SEGT(int x){
		sz = x+3;
		tree.assign(4 * sz , 0);
	}
	void _update(int ind , int l , int r , int qp , int qv){
		if(l == r){
			tree[ind] = qv;
			return;
		}
		int mid = (l+r)/2;
		if(mid >= qp)_update(ind*2 ,l , mid , qp , qv);
		else _update(ind*2+1 , mid+1 , r , qp , qv);
		tree[ind] = tree[ind*2] + tree[ind*2+1];
	}
	void update(int p , int v){
		_update(1,1,sz,p,v);
	}
	int _query(int ind , int l,  int r , int ql , int qr){
		if(l >= ql and r <= qr)return tree[ind];
		else if(l > qr or r < ql)return 0;
		int mid = (l+r)/2;
		return _query(ind*2 , l , mid , ql , qr) + _query(ind*2+1,mid+1,r,ql,qr);
	}
	int query(int l , int r){return _query(1,1,sz,l,r);}
};
int find_inversions(vector < int > a){
	SEGT segt((int)a.size()+5);
	int ret = 0;
	for(int i = a.size()-1;i>=0;i--){
		int res = segt.query(1,a[i]);
		ret += res;
		segt.update(a[i] , 1);
	}
	return ret;
}
int convert(int n , string &a , string &b){
	queue < int > ata[26];
	for(int i = 0;i<n;i++)ata[b[i] - 'a'].push(i);
	vector < int > perm;
	for(int i = 0;i<n;i++){
		perm.push_back(ata[a[i] - 'a'].front() + 1);
		ata[a[i] - 'a'].pop();
	}
	return find_inversions(perm);
}
void solve(){
	int n,ans=0;cin >> n;
	vector < int > ind[26];
	int g[2 * n];
	memset(g , 0 , sizeof(g));
	string str,s1,s2;
	cin >> str;
	for(int i = 0;i<2*n;i++){
		ind[str[i]-'a'].push_back(i);
	}
	for(int i = 0;i<26;i++){
		int sz = (int)ind[i].size();
		for(int j = 0;j < (sz/2);j++){
			g[ind[i][j]] = 1;
		}
	}
	int cnt0 = 0;// 1 ler için , benden önceki 0 lar
	for(int i = 0;i<2 * n;i++){
		if(g[i] == 1)ans += cnt0;
		else cnt0++;
	}
	for(int i = 0;i<2 * n;i++){
		if(g[i] == 0)s1 += str[i];
		else s2 += str[i];
	}
	ans += convert(n,s1,s2);
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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