Submission #855934

#	Time	Username	Problem	Language	Result	Execution time	Memory
855934		NotLinux	Ekoeko (COCI21_ekoeko)	C++17	10 / 110	25 ms	9196 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] = max(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 max(_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] , res+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();
	}
	//cout << "perm : ";for(auto itr : perm)cout << itr << " ";cout << endl;
	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;
		}
	}
	//cout << "g : ";for(int i = 0;i<2*n;i++)cout << g[i] << " ";cout << endl;
	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];
	}
	//cout << ans << " " << s1 << " " << s2 << endl;
	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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40