Submission #1001321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001321		mostafa133	Ekoeko (COCI21_ekoeko)	C++14	110 / 110	52 ms	7900 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const ll mod = 998244353;
ld fpow(ll a, ll b, ll m = -1)
{
	if (m != -1)
		a %= m;
	ll res = 1;
	while (b > 0)
	{
		if (b % 2 == 1)
		{
			if (m != -1)
				res = res * a % m;
			else
			{
				res *= a;
			}
		}
		a = a * a;
		if (m != -1)
		{
			a %= m;
		}
		b /= 2;
	}
	return res;
}
int main()
{
	fast;
	// freopen("pails.in", "r", stdin);
	// freopen("pails.out", "w", stdout);
	ll t = 1;
	// cin >> t;
	while (t--)
	{
		ll n;
		cin >> n;
		string s;
		cin >> s;
		vector<ll> freq(200);
		for (int i = 0; i < 2 * n; i++)
		{
			freq[s[i]]++;
		}
		string s2, t;
		vector<ll> freq2(200);
		ll ans = 0;
		for (int i = 0; i < 2 * n; i++)
		{
			freq2[s[i]]++;
			if (freq2[s[i]] > freq[s[i]] / 2)
			{
				t.push_back(s[i]);
			}
			else
			{
				s2.push_back(s[i]);
				ans+=t.size();
			}
		}

		// cout << t << ' ';
		vector<set<ll>> v(200);
		for (int i = 0; i < n; i++)
		{
			v[t[i]].insert(i);
		}
		ordered_set os;
		for (int i = 0; i < n; i++)
		{
			// if (v[s[i]].empty())
			// continue;
			os.insert(*v[s2[i]].begin());
			ans += (*v[s2[i]].begin()) - os.order_of_key(*v[s2[i]].begin());
			// cout << ans << ' ';
			v[s2[i]].erase(v[s2[i]].begin());
		}
		cout << ans << '\n';
	}
	return 0;
}

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