Submission #880139

#	Time	Username	Problem	Language	Result	Execution time	Memory
880139		Youssif_Elkadi	Ekoeko (COCI21_ekoeko)	C++17	110 / 110	7 ms	2024 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 5, mod = 1e9 + 7, inf = 1e9 + 5;
int tree[N];
long long nr;
void update(int idx, int val)
{
	while (idx <= nr)
	{
		tree[idx] += val;
		idx += idx & -idx;
	}
	return;
}
int query(int idx)
{
	int ret = 0;
	while (idx)
	{
		ret += tree[idx];
		idx -= idx & -idx;
	}
	return ret;
}
int freq[26];
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	long long n;
	cin >> n;
	string x;
	cin >> x;
	for (int i = 0; i < n * 2; i++)
		freq[x[i] - 'a']++;
	long long ans = 0;
	string tmp1, tmp2, tmp3, tmp4;
	int vis[26] = {};
	for (int i = 0; i < n; i++)
	{
		vis[x[i] - 'a']++;
		if (vis[x[i] - 'a'] > freq[x[i] - 'a'] / 2)
			tmp2.push_back(x[i]);
		else
			tmp1.push_back(x[i]);
	}
	int p = n;
	for (int i = n - 1; i >= 0; i--)
	{
		if (vis[x[i] - 'a'] > freq[x[i] - 'a'] / 2)
			ans += p - i - 1, p--;
		vis[x[i] - 'a']--;
	}
	for (int i = n * 2 - 1; i >= n; i--)
	{
		vis[x[i] - 'a']++;
		if (vis[x[i] - 'a'] > freq[x[i] - 'a'] / 2)
			tmp4.push_back(x[i]);
		else
			tmp3.push_back(x[i]);
	}
	reverse(tmp4.begin(), tmp4.end());
	reverse(tmp3.begin(), tmp3.end());
	p = n;
	for (int i = n; i < 2 * n; i++)
	{
		if (vis[x[i] - 'a'] > freq[x[i] - 'a'] / 2)
			ans += i - p, p++;
		vis[x[i] - 'a']--;
	}
	string a, b;
	a = tmp1 + tmp4, b = tmp2 + tmp3;
	nr = a.size();
	ans += 1LL * tmp4.size() * tmp2.size();
	vector<queue<int>> ind(26);
	for (int i = 0; i < b.size(); i++)
		ind[b[i] - 'a'].push(i);
	for (int i = 0; i < a.size(); i++)
	{
		ans += ind[a[i] - 'a'].front() - query(ind[a[i] - 'a'].front() + 1);
		update(ind[a[i] - 'a'].front() + 1, 1);
		ind[a[i] - 'a'].pop();
	}
	cout << ans << "\n";
}
/*
4
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = 0; i < b.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~

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