oj.uz

Submission #274938

# Submission time Handle Problem Language Result Execution time Memory
274938 2020-08-20T01:49:44 Z c4ts0up Arranging Shoes (IOI19_shoes) C++17
10 / 100
 3 ms 2816 KB 
/*
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;
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 ms 2720 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Incorrect 2 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Incorrect 2 ms 2688 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 ms 2720 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 ms 2720 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Incorrect 2 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -