Submission #1003819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003819		vjudge1	Ekoeko (COCI21_ekoeko)	C++17	0 / 110	4 ms	4068 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
#define v1 v

using namespace std;

const int N = 200010;

vector <int> c[26];
vector <pair <int, int>> v;

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;

int main(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	for(int i = 0;i < 2*n;i++){
		c[s[i] - 'a'].push_back(i);
	}
	for(int i = 0;i < 26;i++){
		int t = c[i].size();
		t /= 2;
		for(int j = t;j < c[i].size();i++){
			v.push_back({c[i][j-t], c[i][j]-n});
		}
	}
	sort(v.begin(), v.end());
	for(auto &x : v){
		x.first++;
		x.second++;
	}
	int at = 1;
	int res = 0;
	for(auto &x : v){
		if(x.first > at){
			res += x.first-at;
			x.first = at;
		}
		at++;
	}
	for(auto &x : v)
		swap(x.first, x.second);
	sort(v.begin(), v.end());
	for(auto &x : v)
		swap(x.first, x.second);
	for(auto x : v){
		res += seg.query(1, x.first, n, 1, n);
		seg.update(1, 1, n, x.first, 1);
	}
	cout << res << endl;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int j = t;j < c[i].size();i++){
      |                 ~~^~~~~~~~~~~~~

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