Submission #235782

#	Time	Username	Problem	Language	Result	Execution time	Memory
235782		FlowerOfSorrow	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 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;
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> a(2 * n);
	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();
	}
	cout << res;
	return 0;
}

/*

*/

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

Compilation message (stderr)

/tmp/cc6Dj9Li.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccjrzA8q.o:shoes.cpp:(.text.startup+0x0): first defined here
/tmp/cc6Dj9Li.o: In function `main':
grader.cpp:(.text.startup+0x282): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status