Submission #276818

#	Time	Username	Problem	Language	Result	Execution time	Memory
276818		c4ts0up	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	333 ms	61436 KiB

shoes

/*
ID: c4ts0up
LANG: C++
TASK: 
*/

#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[5*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);
		}
	}
	
	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;
vector <ll> arr;

ll count_swaps(vector<int> s) {
	ll cambios = 0;
	n = s.size()/2;
	
	set <ll> seen;
	ST = SegTree(0, 2*n);
	
	arr.resize(2*n+5);
	for (int i=0; i<2*n; i++) {
		arr[i] = s[i];
		p[arr[i]+100000].insert(i);
	}
	
	//cerr << "Posiciones guardadas" << endl;
	
	
	for (int i=0; i<2*n; i++) {
		// ya visitamos su pareja izquierda
		if (seen.count(i)) continue;
		
		ll val = arr[i], c1, c2;
		cambios += (val > 0);
		c1 = *(p[val+100000].begin()), c2 = *(p[-val+100000].begin());
		
		/*//
		cerr << "val = " << val << "; c1 = " << c1 << "(+ " << ST.get(c1) << "), c2 = " << c2 << "(+ " << ST.get(c2) << ")" << endl;
		//*/
		
		cambios += (c2 + ST.get(c2))-(c1 + ST.get(c1))-1;
		
		ST.update(c1, c2 + (ST.get(c2)-ST.get(c1)), 1); ///////////////////////////////////////////////////////////////////////// las posiciones cambian
		
		// los eliminamos
		p[val+100000].erase(p[val+100000].begin());
		p[-val+100000].erase(p[-val+100000].begin());
		
		// lo visitamos
		seen.insert(c1);
		seen.insert(c2);
	}
	
	//cerr << "Se realizaron " << cambios << endl;
	return cambios;
}

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