oj.uz

Submission #880139

# Submission time Handle Problem Language Result Execution time Memory
880139 2023-11-28T20:02:19 Z Youssif_Elkadi Ekoeko (COCI21_ekoeko) C++17
110 / 110
 7 ms 2024 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 4 ms 1256 KB Output is correct
4 Correct 5 ms 1764 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 4 ms 1256 KB Output is correct
4 Correct 5 ms 1764 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 4 ms 1256 KB Output is correct
4 Correct 5 ms 1764 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1768 KB Output is correct
7 Correct 6 ms 2024 KB Output is correct
8 Correct 5 ms 2024 KB Output is correct
9 Correct 5 ms 1856 KB Output is correct
10 Correct 5 ms 2020 KB Output is correct
11 Correct 5 ms 2024 KB Output is correct
12 Correct 6 ms 1768 KB Output is correct
13 Correct 5 ms 1768 KB Output is correct
14 Correct 6 ms 1768 KB Output is correct
15 Correct 5 ms 1768 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 4 ms 1256 KB Output is correct
4 Correct 5 ms 1764 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 7 ms 1768 KB Output is correct
11 Correct 6 ms 2024 KB Output is correct
12 Correct 5 ms 2024 KB Output is correct
13 Correct 5 ms 1856 KB Output is correct
14 Correct 5 ms 2020 KB Output is correct
15 Correct 5 ms 2024 KB Output is correct
16 Correct 6 ms 1768 KB Output is correct
17 Correct 5 ms 1768 KB Output is correct
18 Correct 6 ms 1768 KB Output is correct
19 Correct 5 ms 1768 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 464 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 6 ms 2024 KB Output is correct
33 Correct 6 ms 1932 KB Output is correct
34 Correct 6 ms 2020 KB Output is correct
35 Correct 6 ms 1972 KB Output is correct
36 Correct 6 ms 2020 KB Output is correct
37 Correct 6 ms 2020 KB Output is correct
38 Correct 5 ms 1768 KB Output is correct
39 Correct 5 ms 1952 KB Output is correct
40 Correct 5 ms 1788 KB Output is correct
41 Correct 5 ms 1924 KB Output is correct