oj.uz

Submission #1003834

# Submission time Handle Problem Language Result Execution time Memory
1003834 2024-06-20T18:41:31 Z vjudge1 Ekoeko (COCI21_ekoeko) C++17
20 / 110
 32 ms 6760 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 200010;

vector <int> c[26];

struct Segtree{
	int tree[4*N];
	Segtree(){
		for(int i = 0;i < 4*N;i++) tree[i] = 0;
	}
	int join(int a, int b){
		return a+b;
	}
	void update(int node, int l, int r, int pos, int val){
		if(l == r){
			tree[node] += val;
			return;
		}
		int mid=  (l+r)/2;
		if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
		else update(2*node+1, mid+1, r, pos, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		if(l > tr or tl > r) return 0;
		if(l <= tl and tr <= r) return tree[node];
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl , mid), query(2*node+1, l, r, mid+1, tr));
	}
}seg;

vector <int> srt;
int tam[26];

int main(){
	int n;
	cin>> n;
	string s;
	cin >> s;
	vector <int> v1, v2;
	for(int i = 0;i < 2*n;i++){
		c[s[i]-'a'].push_back(i+1);
	}
	for(int i = 0;i < 26;i++){
		tam[i] = c[i].size();
		tam[i] /= 2;
		tam[i]--;
	}
	for(int i = 2*n;i > 0;i--){
		if(tam[s[i-1]-'a'] < 0) continue;
		c[s[i-1]-'a'].pop_back();
		v2.push_back(i);
		v1.push_back(c[s[i-1]-'a'][tam[s[i-1]-'a']]);
		tam[s[i-1]-'a']--;
	}
	reverse(v1.begin(), v1.end());
	reverse(v2.begin(), v2.end());
	for(auto x : v1) srt.push_back(x);
	for(auto x : v2) srt.push_back(x);
	int res = 0;
	for(auto x : srt){
		//cout << x << ' ';
		res += seg.query(1,x, 2*n, 1, 2*n);
		seg.update(1, 1, 2*n, x, 1);
	}
	cout << res << endl;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 10 ms 4756 KB Output is correct
3 Correct 19 ms 6248 KB Output is correct
4 Incorrect 32 ms 6760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 10 ms 4756 KB Output is correct
3 Correct 19 ms 6248 KB Output is correct
4 Incorrect 32 ms 6760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 10 ms 4756 KB Output is correct
3 Correct 19 ms 6248 KB Output is correct
4 Incorrect 32 ms 6760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 1 ms 3568 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 1 ms 3388 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 1 ms 3568 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 10 ms 4756 KB Output is correct
3 Correct 19 ms 6248 KB Output is correct
4 Incorrect 32 ms 6760 KB Output isn't correct
5 Halted 0 ms 0 KB -