Submission #267175

#	Time	Username	Problem	Language	Result	Execution time	Memory
267175		c4ts0up	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	3 ms	2728 KiB

shoes

#include "shoes.h"
/*
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;
vector <ll> p[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;

ll count_swaps(vector<int> s) {
	ll cambios = 0;
	n = s.size()/2;
	
	set <ll> seen;
	ST = SegTree(0, 2*n);
	
	for (int i=0; i<2*n; i++) {
		if (p[abs(s[i])].empty() && s[i] > 0) cambios++; // toca hacer un cambios de mas
		
		p[abs(s[i])].pb(i);
	}
	
	//cerr << "Posiciones guardadas" << endl;
	
	
	for (int i=0; i<2*n; i++) {
		// ya visitamos su pareja izquierda
		if (seen.count(abs(s[i]))) continue;
		
		ll c1 = p[abs(s[i])][0], c2 = p[abs(s[i])][1];
		
		//cerr << "Vamos a visitar el zapato con numero " << abs(s[i]) << ". ";
		//cerr << "c1 = " << c1 << ", c2 = " << c2 << endl;
		
		c1 += ST.get(c1);
		c2 += ST.get(c2);
		
		//cerr << "Con quieries: " << "c1 = " << c1 << ", c2 = " << c2 << endl;
		cambios += c2-c1-1;
		
		ST.update(p[abs(s[i])][0], p[abs(s[i])][1], 1);
		
		// lo visitamos
		seen.insert(abs(s[i]));
	}
	
	//cerr << "Se realizaron " << cambios << endl;
	return cambios;
}

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