Submission #868998

#	Time	Username	Problem	Language	Result	Execution time	Memory
868998		Cyber_Wolf	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	13 ms	6188 KiB

Main

// Problem: Writing Numbers
// Contest: CSES - CSES Problem Set
// URL: https://cses.fi/problemset/task/1086
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

#define lg long long 

const lg N = 2e5+5;

vector<lg> a[27];
lg loc[N], bit[N], m;

lg get(lg idx)
{
	lg ans = 0;
	while(idx)
	{
		ans += bit[idx];
		idx -= (idx&(-idx));
	}
	return ans;
}

void upd(lg idx)
{
	while(idx <= m)
	{
		bit[idx]++;
		idx += (idx&(-idx));
	}
}

int main()
{
	lg n;
	string s;
	cin >> n >> s;
	m = 2*n;
	for(int i = 0; i < n*2; i++)
	{
		a[s[i]-'a'].push_back(i);
	}
	for(int i = 0; i < 26; i++)
	{
		lg x = a[i].size()/2;
		for(int j = 0; j < x; j++)
		{
			loc[a[i][j]] = -1;
			loc[a[i][j+x]] = 1;
		}
		a[i].clear();
	}
	string c = "", d = "";
	lg ans = 0;
	for(int i = 0; i < n*2; i++)	
	{
		if(loc[i] == -1)	c += s[i], ans += d.size(), loc[i] = c.size()-1;
		else	d += s[i], loc[i] = d.size()+n-1;
	}
	s = c+d;
	for(int i = 0; i < n*2; i++)
	{
		a[s[i]-'a'].push_back(i);
	}
	for(int i = 0; i < 26; i++)
	{
		lg x = a[i].size()/2;
		for(int j = 0; j < x; j++)
		{
			loc[a[i][j]] = a[i][j];
			loc[a[i][j+x]] = loc[a[i][j]]+n;
		}
	}
	for(int i = 2*n-1; i+1; i--)
	{
		ans += get(loc[i]+1);
		upd(loc[i]+1);
	}
	cout << ans << '\n';
}

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