Submission #255726

#	Time	Username	Problem	Language	Result	Execution time	Memory
255726		jainbot27	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	467 ms	28408 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;
	// cerr << "N " << n << endl;
	Seg<int> seg;
	map<int, vector<int>> mp;
	vector<int> seen(2 * n, 0);
	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>());
		// cerr << z.first << " ";
		// for(auto& v : z.second){
			// cerr << v << " " ;
		// }
		// cerr << endl;
	}
	ll ans = 0;
	seg.init(2 * n);
	for(int i = 0; i < 2 * n; i++){
		if(!seen[i]){
			int x = mp[-S[i]].back();
			seen[x] = 1;
			seen[i] = 1;
			mp[-S[i]].pop_back();
			mp[S[i]].pop_back();
			int pos1 = i + seg.query(0, i);
			int pos2 = x + seg.query(0, x);
			if(((pos2 < pos1) && S[i] < 0) || (S[i] > 0 && pos1 < pos2)){
				ans++;
			}
			// cerr << "POS1 " << i << " POS2 " << x << endl;
			ans += abs(pos2 - pos1 - 1);
			seg.update(i + 1, 1);
			seg.update(x, -1);
		}
	}
	return ans;
}


// int main(){
// 	vector<int> arr = {2, 1, -1, -2};
// 	cout << count_swaps(arr) << endl;
// }

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