제출 #1163434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163434		salmon	Ekoeko (COCI21_ekoeko)	C++20	110 / 110	69 ms	16084 KiB

Main

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

int N;
int cont[30];
int tcont[30];
string s;
map<pair<int,int>,int> mep;
int num = 0;

struct node{
	
	int s, e, m;
	int v;
	node *l , *r;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		v = e - s + 1;
		
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1, e);
		}
	}
	
	
	void update(int i){
		v--;
		
		if(s != e){
			if(i <= m) l -> update(i);
			else r-> update(i);
		}
	}
	
	int query(int S, int E){
		if(S <= s && e <= E) return v;
		int V = 0;
		if(S <= m) V += l -> query(S,E);
		if(m <  E) V += r -> query(S,E);
		return V;
	}
}*root;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N;
	cin >> s;

	N *= 2;

	for(int i = 0; i <= 26; i++) cont[i] = 0;
	for(int i = 0; i <= 26; i++) tcont[i] = 0;
	
	for(int i = 0; i < N; i++){
		cont[s[i] - 'a']++; 
	}

	root = new node(0,N/2 - 1);
	
	long long int ans = 0;
	int cant = 0;
	
	for(int i = 0; i < N; i++){
		tcont[s[i] - 'a']++;
		
		if(tcont[s[i] - 'a'] <= cont[s[i]-'a']/2){
			mep[{s[i]-'a',tcont[s[i] - 'a']}] = num;
			num++;
			ans += cant;
		}
		else{
			cant++;
		}
	}
	
	for(int i = 0; i <= 26; i++) tcont[i] = 0;
	
	for(int i = 0; i < N; i++){
		tcont[s[i] - 'a']++;
		
		if(tcont[s[i] - 'a'] > cont[s[i]-'a']/2){
			root -> update(mep[{s[i]-'a',tcont[s[i] - 'a'] - cont[s[i]-'a']/2}]);
			ans += root -> query(0,mep[{s[i]-'a',tcont[s[i] - 'a'] - cont[s[i]-'a']/2}]);
		}
	}
	
	
	printf("%lld",ans);
}

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