Submission #1265954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265954		namhh	Ekoeko (COCI21_ekoeko)	C++20	110 / 110	10 ms	8328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
int n,cnt[N],cnt1[N],cnt2[N],cnt3[N],bits[N];
string s,a,b,c,d,p,q;
vector<int>cc1,cc2,adj[N];
void update(int u){
	while(u > 0){
		bits[u]++;
		u -= u & (-u);
	}
}
int get(int u){
	int sum = 0;
	while(u <= n){
		sum += bits[u];
		u += u & (-u);
	}
	return sum;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> s;
	s = "#"+s;
	for(int i = 1; i < s.size(); i++) cnt[s[i]-'a']++;
	for(int i = 1; i <= n; i++){
		cnt1[s[i]-'a']++;
		if(cnt1[s[i]-'a'] > cnt[s[i]-'a']/2){
		    b += s[i];
		    cc1.push_back(i);
		}
		else a += s[i];
	}
	for(int i = s.size()-1; i > n; i--){
		cnt2[s[i]-'a']++;
		if(cnt2[s[i]-'a'] > cnt[s[i]-'a']/2){
		    d += s[i];
		    cc2.push_back(i);
		}
		else c += s[i];
	}
	int x = b.size();
	int ans = x*x;
	for(int i = 0; i < cc1.size(); i++) ans += n-(cc1.size()-i-1)-cc1[i];
	for(int i = 0; i < cc2.size(); i++) ans += cc2[i]-n-1-i;
	reverse(c.begin(),c.end());
	reverse(d.begin(),d.end());
	p = "#"+a+d;
	q = "#"+b+c;
	for(int i = 1; i <= n; i++) adj[q[i]-'a'].push_back(i);
	for(int i = 1; i <= n; i++){
		int x = p[i]-'a';
		int pos = adj[x][cnt3[x]];
		pos += get(pos);
		ans += pos-i;
		update(adj[x][cnt3[x]]);
		cnt3[x]++;
	}
	cout << ans;
}
//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--

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