Submission #235784

#	Time	Username	Problem	Language	Result	Execution time	Memory
235784		FlowerOfSorrow	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	66 ms	10232 KiB

shoes

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/rope"
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(high_resolution_clock::now().time_since_epoch().count());
#define lambdify(x) [&](auto &&...args){ return x(forward<decltype(args)>(args)...); }
template<typename T, typename U> T &ctmax(T &x, const U &y){ return x = max<T>(x, y); }
template<typename T, typename U> T &ctmin(T &x, const U &y){ return x = min<T>(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct segment{
	int n;
	vector<int> val;
	segment(int n): n(n), val(n << 1, 1){
		for(auto i = n - 1; i > 0; -- i){
			val[i] = val[i << 1] + val[i << 1 ^ 1];
		}
	}
	void update(int p, int x){
		for(val[p += n] += x; p > 1; p >>= 1){
			val[p >> 1] = val[p] + val[p ^ 1];
		}
	}
	int query(int l, int r){
		int res = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1){
			if(l & 1){
				res += val[l ++];
			}
			if(r & 1){
				res += val[-- r];
			}
		}
		return res;
	}
};

long long count_swaps(vector<int> a){
	int n = int(a.size()) / 2;
	vector<vector<int>> pos(n);
	long long res = 0;
	for(auto i = 0; i < 2 * n; ++ i){
		cin >> a[i];
		if(int(pos[abs(a[i]) - 1].size()) % 2 && a[i] < 0){
			++ res;
		}
		a[i] = abs(a[i]) - 1;
		pos[a[i]].push_back(i);
	}
	segment tr(2 * n);
	for(auto i = 2 * n - 1; i >= 0; -- i){
		if(int(pos[a[i]].size()) % 2 == 0){
			int p = *next(pos[a[i]].rbegin());
			res += tr.query(p + 1, i);
			tr.update(p, -1);
		}
		pos[a[i]].pop_back();
	}
	return res;
}

/*int main(){
	cin.tie(0)->sync_with_stdio(0);

	return 0;
}*/

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

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