Submission #255724

#	Time	Username	Problem	Language	Result	Execution time	Memory
255724		jainbot27	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	0 ms	384 KiB

shoes

#include <bits/stdc++.h>
#include <shoes.h>
using namespace std;
using ll = long long;

template<class T> struct Seg {
	const T sta = 0;
	T comb(T a, T b){
		return a + b; 
	}
	int n; vector<T> seg;
	void init(int nn){
		n = nn;
		seg.assign(3*n, sta);
	}
	void pull(int q){
		seg[q] = comb(seg[2*q], seg[2*q+1]);
	}
	void update(int q, T val){
		seg[q+=n] += val; for(q/=2; q!=0;q/=2) pull(q);
	}
	T query(int l, int r){
		T ri = sta, la = sta;
		for(l += n, r+= n+1; l < r; l/=2, r/=2){
			if(l&1) ri = comb(ri, seg[l++]);
			if(r&1) la = comb(seg[--r], la);
		}
		return comb(ri, la);
	}
};


ll count_swaps(vector<int> S){
	int n = S.size()/2;
	Seg<int> seg;
	map<int, vector<int>> mp;
	for(int i=0; i < 2*n; i++){
		mp[S[i]].push_back(i);
	}
	for(auto&z : mp){
		sort(z.second.begin(), z.second.end(), greater<int>());
	}
	ll ans = 0;
	seg.init(2 * n);
	for(int i = 0; i < 2 * n; i++){
		if(S[i]<0){
			int x = mp[-S[i]].back();
			mp[-S[i]].pop_back();
			int pos1 = i + seg.query(0, i);
			int pos2 = x + seg.query(0, x);
			if(pos2 > pos1){
				ans++;
				swap(pos1, pos2);
			}
			ans += pos2 - pos1 - 1;
			seg.update(pos1 + 1, 1);
			seg.update(pos2, -1);
		}
	}
	return ans;
}

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