oj.uz

Submission #880130

# Submission time Handle Problem Language Result Execution time Memory
880130 2023-11-28T19:47:52 Z Youssif_Elkadi Ekoeko (COCI21_ekoeko) C++17
30 / 110
 6 ms 1888 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;
}
bool sub1(string x)
{
	char hi1 = x[0], hi2 = x[x.size() - 1];
	for (int i = 0; i < x.size() / 2; i++)
		if (hi1 != x[i])
			return 0;
	for (int i = x.size() / 2; i < x.size(); i++)
		if (hi2 != x[i])
			return 0;
		else
			return 1;
}
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;
	if (sub1(x))
	{
		return cout << (n / 2) * (n / 2) << "\n", 0;
	}
	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'] == 2)
			tmp2.push_back(x[i]);
		else
			tmp1.push_back(x[i]);
	}
	int p = n;
	for (int i = n - 1; i >= 0; i--)
	{
		vis[x[i] - 'a']--;
		if (vis[x[i] - 'a'])
			ans += p - i - 1, p--;
	}
	for (int i = n * 2 - 1; i >= n; i--)
	{
		vis[x[i] - 'a']++;
		if (vis[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++)
	{
		vis[x[i] - 'a']--;
		if (vis[x[i] - 'a'])
			ans += i - p, p++;
	}
	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 'bool sub1(std::string)':
Main.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 0; i < x.size() / 2; i++)
      |                  ~~^~~~~~~~~~~~~~
Main.cpp:31:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i = x.size() / 2; i < x.size(); i++)
      |                             ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0; i < b.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp: In function 'bool sub1(std::string)':
Main.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
   36 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 744 KB Output is correct
4 Correct 1 ms 744 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 0 ms 604 KB Output is correct
3 Correct 0 ms 744 KB Output is correct
4 Correct 1 ms 744 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 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 744 KB Output is correct
4 Correct 1 ms 744 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 6 ms 1888 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 744 KB Output is correct
4 Correct 1 ms 744 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 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 6 ms 1888 KB Output isn't correct
11 Halted 0 ms 0 KB -