oj.uz

Submission #1003926

# Submission time Handle Problem Language Result Execution time Memory
1003926 2024-06-20T20:15:07 Z vjudge1 Ekoeko (COCI21_ekoeko) C++17
20 / 110
 6 ms 7476 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
array<int, MAXN> bit;

void update(int id, int val)
{
	while (id < MAXN)
	{
		bit[id] += val;
		id += id&-id;
	}
}

int query(int id)
{
	int resp = 0;
	while (id > 0)
	{
		resp += bit[id];
		id -= id&-id;
	}
	return resp;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	string s;
	cin >> s;
	vector<vector<int>> freq(30);
	for (int i = 0; i < 2*N; i++) freq[s[i]-'a'].push_back(i);
	vector<int> v1(2*N);
	vector<pair<int, int>> pares;
	for (int c = 0; c < 30; c++)
	{
		int sz = freq[c].size();
		for (int i = 0; i < sz/2; i++) 
		{
			v1[freq[c][i]] = 0; v1[freq[c][i+sz/2]] = 1;
			pares.emplace_back(freq[c][i], freq[c][i+sz/2]);
		}
	}
	int resp = 0, cnt1 = 0;
	for (int i = 0; i < 2*N; i++)
	{
		if (v1[i]) cnt1++;
		else resp += cnt1;
	}

	sort(pares.rbegin(), pares.rend());
	for (auto &[x, y] : pares)
	{
		resp += query(y);
		update(y, +1);
	}
	cout << resp << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 2712 KB Output is correct
3 Runtime error 6 ms 7476 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 2712 KB Output is correct
3 Runtime error 6 ms 7476 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 2712 KB Output is correct
3 Runtime error 6 ms 7476 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 424 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 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 2712 KB Output is correct
3 Runtime error 6 ms 7476 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -