Submission #1186811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186811		hamzabc	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	229 ms	20764 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>


using namespace std;
#define all(x) x.begin(), x.end()
#define sp << " " << 


class segtre{
private:
	int sz;
	vector<int> tre;
	void _update(int x, int d, int l, int r, int s){
		if (l > x || r < x)
			return;
		if (l == r){
			tre[s] += d;
			return;
		}
		int m = (l + r) >> 1;
		_update(x, d, l, m, s << 1);
		_update(x, d, m + 1, r, (s << 1) | 1);
		tre[s] = tre[s << 1] + tre[(s << 1) | 1];
	}

	int _query(int tl, int tr, int l, int r, int s){
		if (l > tr || r < tl)
			return 0;
		if (tl <= l && r <= tr){
			return tre[s];
		}
		int m = (l + r) >> 1;
		return _query(tl, tr, l, m, s << 1) + _query(tl, tr, m + 1, r, (s << 1) | 1);
	}
public:
	void init(int size){
		sz = size;
		tre.resize(size * 4);
	}

	void update(int konum, int add){
		_update(konum, add, 0, sz - 1, 1);
	}
	
	int query(int l, int r){
		return _query(l, r, 0, sz - 1, 1);
	}
};


long long count_swaps(std::vector<int> s) {
	segtre tre;
	int n = s.size();
	tre.init(n);

	map<int, vector<int>> zip;
	int j = 1;
	for (int i = 0; i < n; i++){
		if (s[i] < 0)
			continue;
		zip[-s[i]].push_back(-j);
		s[i] = j;
		j++;
	}
	for (int i = n - 1; i >= 0; i--){
		if (s[i] > 0)
			continue;
		int tmp = s[i];
		s[i] = zip[tmp].back();
		zip[tmp].pop_back();
	}


	long long int ret = 0;
	map<int, int> mp;
	for (int i = 0; i < n; i++){
		if (mp[abs(s[i])]){
			ret += i - mp[abs(s[i])];
			if (s[i] < 0)
				ret += 1;
			tre.update(i, -1);
			mp[abs(s[i])] = i;
		}else{
			mp[abs(s[i])] = i + 1;
			tre.update(i, 1);
		}
	}
	for (int i = 0; i < n; i++){
		if (s[i] == 0)
			continue;
		ret -= tre.query(i, mp[abs(s[i])]);
		// tre.update(i, -1); // this doesn't needed
		tre.update(mp[abs(s[i])], 1);
		s[mp[abs(s[i])]] = 0;
	}
	return ret;
}

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