Submission #235845

#	Time	Username	Problem	Language	Result	Execution time	Memory
235845		FlowerOfSorrow	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	317 ms	75896 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;
	map<int, queue<int>> q;
	vector<int> paired(2 * n, -1);
	for(auto i = 0; i < 2 * n; ++ i){
		if(q.count(-a[i])){
			auto &c = q[-a[i]];
			paired[c.front()] = i;
			c.pop();
			if(c.empty()){
				q.erase(-a[i]);
			}
		}
		else{
			q[a[i]].push(i);
		}
	}
	segment tr(2 * n);
	long long res = 0;
	for(auto i = 0; i < 2 * n; ++ i){
		if(~paired[i]){
			if(a[i] > 0){
				++ res;
			}
			int j = paired[i];
			res += tr.query(i + 1, j);
			tr.update(j, -1);
		}
	}
	return res;
}

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