Submission #1219783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219783		nikd	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	303 ms	35668 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

struct segtree{
	int n; vector<int> t;
	segtree(vector<int> &a): n(a.size()){
		t.resize(2*n);
		for(int i = 0; i<n; i++) t[i+n] = a[i];
		for(int i = n-1; i > 0; i--) t[i] = t[i<<1] + t[(i<<1) | 1];
	}
	void upd(int i, int k){
		for(t[i+=n] = k; i>>=1; ) t[i] = t[i<<1] + t[(i<<1) | 1];
		return;
	}
	int q(int l, int r){
		int sol = 0;
		for(l+=n, r+=n; l<=r; l>>=1, r>>=1){
			if(l&1) sol += t[l++];
			if(!(r&1)) sol += t[r--];
		}
		return sol;
	}
};

long long count_swaps(std::vector<int> s) {
	map<int, vector<int>> idx;
	int n = (int)s.size();
	for(int i = 0; i<n; i++) idx[s[i]].push_back(i);
	map<int, int> point;
	for(int i = 0; i<n; i++) point[s[i]] = 0;
	vector<int>vv(n, 1);
	segtree sg(vv);
	long long sol = 0;
	vector<bool> vis(n, 0);
	for(int i = 0; i<n; i++){
		if(vis[i]) continue;
		int r = idx[-s[i]][point[-s[i]]];
		point[s[i]]++;
		point[-s[i]]++;
		if(r > i+1){
			sol += sg.q(i+1, r-1);
		} 
		if(s[i] > 0) sol++;
		sg.upd(i, 0);
		vis[i] = 1;
		sg.upd(r, 0);
		vis[r] = 1;
	}
	return sol;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15