Submission #277048

#	Time	Username	Problem	Language	Result	Execution time	Memory
277048		c4ts0up	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	457 ms	47224 KiB

shoes

/*
ID: c4ts0up
LANG: C++
TASK: Shoes - IOI 2019
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define ff first
#define ss second

const ll NMAX = 100002;

ll n;
set <ll> p[2*NMAX];

struct SegTree {
	ll l, r, mid, suma, lazy;
	SegTree *left, *right;
	
	SegTree () {}
	SegTree (ll lb, ll ub) {
		l = lb;
		r = ub;
		mid = (l+r)/2;
		suma = 0;
		lazy = 0;
		left = nullptr;
		right = nullptr;
		
		// nodo con hijos
		if (l != r) {
			left = new SegTree(l, mid);
			right = new SegTree(mid+1, r);
		}
		else suma = l;
	}
	
	void propagate() {
		if (lazy) {
			suma += lazy * (r-l+1); // [l, r]
			if (left) left->lazy += lazy;
			if (right) right->lazy += lazy;
			lazy = 0;
		}
	}
	
	void update(ll init, ll fin, ll x) {
		propagate();
		if (init == l && fin == r) {
			lazy += x;
			propagate();
		}
		else {
			if (fin <= mid) left->update(init, fin, x), right->propagate();
			else if (init >= mid+1) left->propagate(), right->update(init, fin, x);
			else left->update(init, mid, x), right->update(mid+1, fin, x);
			suma = left->suma + right->suma;
		}
	}
	
	ll get(ll init, ll fin) {
		//cerr << "curr node: <" << l << ", " << r << ">" << "; looking for [" << init << ", " << fin << "]" << endl;
		
		propagate();
		if (init == l && fin == r) {
			//cerr << "value obtained success" << endl;
			return suma;
		}
		else {
			if (fin <= mid) return left->get(init, fin);
			else if (init >= mid+1) return right->get(init, fin);
			else return left->get(init, mid) + right->get(mid+1, fin);
		}
	}
	
	ll get(ll pos) { return get(pos, pos); }
};

SegTree ST;

ll count_swaps(vector<int> s) {
	ll cambios = 0;
	n = s.size()/2;
	
	set <ll> seen;
	ST = SegTree(0, 2*n+2);
	
	for (int i=0; i<2*n; i++) {
		p[s[i]+100000].insert(i);
	}
	
	for (int i=0; i<2*n; i++) {
		// ya lo vimos
		if (seen.count(i)) continue;
		
		ll val = s[i], c1, c2;
		cambios += (val > 0); // toca hacer el cambio extra
		
		c1 = *(p[val+100000].begin()), c2 = *(p[-val+100000].begin());
		
		cambios += ST.get(c2) - ST.get(c1) -1;
		
		ST.update(c1, c2, 1);
	
		p[val+100000].erase(p[val+100000].begin());
		p[-val+100000].erase(p[-val+100000].begin());
	
		seen.insert(c1);
		seen.insert(c2);
	}
	
	//cerr << "Se realizaron " << cambios << endl;
	return cambios;
}

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