Submission #276815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
276815	2020-08-20T16:56:09 Z	c4ts0up	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	320 ms	48636 KB

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[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);
		}
	}
	
	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.0 / 10.0

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

Subtask #2
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9728 KB	Output is correct
2	Correct	7 ms	9728 KB	Output is correct
3	Correct	7 ms	9760 KB	Output is correct
4	Correct	8 ms	9728 KB	Output is correct
5	Correct	8 ms	9728 KB	Output is correct
6	Correct	7 ms	9728 KB	Output is correct
7	Correct	7 ms	9728 KB	Output is correct
8	Correct	7 ms	9728 KB	Output is correct
9	Correct	7 ms	9728 KB	Output is correct
10	Correct	7 ms	9728 KB	Output is correct
11	Correct	8 ms	9728 KB	Output is correct
12	Correct	7 ms	9728 KB	Output is correct
13	Correct	8 ms	9728 KB	Output is correct
14	Correct	6 ms	9728 KB	Output is correct
15	Correct	9 ms	9728 KB	Output is correct
16	Correct	6 ms	9728 KB	Output is correct
17	Correct	9 ms	9728 KB	Output is correct
18	Correct	7 ms	9728 KB	Output is correct
19	Correct	10 ms	9728 KB	Output is correct
20	Correct	7 ms	9728 KB	Output is correct
21	Correct	9 ms	9728 KB	Output is correct
22	Correct	6 ms	9728 KB	Output is correct
23	Correct	8 ms	9728 KB	Output is correct
24	Correct	7 ms	9728 KB	Output is correct
25	Correct	8 ms	9728 KB	Output is correct
26	Correct	7 ms	9728 KB	Output is correct
27	Correct	8 ms	9728 KB	Output is correct
28	Correct	8 ms	9728 KB	Output is correct
29	Correct	7 ms	9728 KB	Output is correct
30	Correct	6 ms	9728 KB	Output is correct
31	Runtime error	19 ms	19456 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-

Subtask #3
0 / 20.0

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

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9728 KB	Output is correct
2	Correct	7 ms	9728 KB	Output is correct
3	Correct	8 ms	9728 KB	Output is correct
4	Correct	6 ms	9728 KB	Output is correct
5	Correct	247 ms	47284 KB	Output is correct
6	Correct	320 ms	48636 KB	Output is correct
7	Correct	236 ms	48504 KB	Output is correct
8	Correct	223 ms	48504 KB	Output is correct
9	Correct	312 ms	48504 KB	Output is correct
10	Correct	250 ms	48504 KB	Output is correct

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9728 KB	Output is correct
2	Correct	7 ms	9728 KB	Output is correct
3	Correct	7 ms	9760 KB	Output is correct
4	Correct	8 ms	9728 KB	Output is correct
5	Correct	8 ms	9728 KB	Output is correct
6	Correct	7 ms	9728 KB	Output is correct
7	Correct	7 ms	9728 KB	Output is correct
8	Correct	7 ms	9728 KB	Output is correct
9	Correct	7 ms	9728 KB	Output is correct
10	Correct	7 ms	9728 KB	Output is correct
11	Correct	8 ms	9728 KB	Output is correct
12	Correct	7 ms	9728 KB	Output is correct
13	Correct	8 ms	9728 KB	Output is correct
14	Correct	6 ms	9728 KB	Output is correct
15	Correct	9 ms	9728 KB	Output is correct
16	Correct	6 ms	9728 KB	Output is correct
17	Correct	9 ms	9728 KB	Output is correct
18	Correct	7 ms	9728 KB	Output is correct
19	Correct	10 ms	9728 KB	Output is correct
20	Correct	7 ms	9728 KB	Output is correct
21	Correct	9 ms	9728 KB	Output is correct
22	Correct	6 ms	9728 KB	Output is correct
23	Correct	8 ms	9728 KB	Output is correct
24	Correct	7 ms	9728 KB	Output is correct
25	Correct	8 ms	9728 KB	Output is correct
26	Correct	7 ms	9728 KB	Output is correct
27	Correct	8 ms	9728 KB	Output is correct
28	Correct	8 ms	9728 KB	Output is correct
29	Correct	7 ms	9728 KB	Output is correct
30	Correct	6 ms	9728 KB	Output is correct
31	Runtime error	19 ms	19456 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9728 KB	Output is correct
2	Correct	7 ms	9728 KB	Output is correct
3	Correct	7 ms	9760 KB	Output is correct
4	Correct	8 ms	9728 KB	Output is correct
5	Correct	8 ms	9728 KB	Output is correct
6	Correct	7 ms	9728 KB	Output is correct
7	Correct	7 ms	9728 KB	Output is correct
8	Correct	7 ms	9728 KB	Output is correct
9	Correct	7 ms	9728 KB	Output is correct
10	Correct	7 ms	9728 KB	Output is correct
11	Correct	8 ms	9728 KB	Output is correct
12	Correct	7 ms	9728 KB	Output is correct
13	Correct	8 ms	9728 KB	Output is correct
14	Correct	6 ms	9728 KB	Output is correct
15	Correct	9 ms	9728 KB	Output is correct
16	Correct	6 ms	9728 KB	Output is correct
17	Correct	9 ms	9728 KB	Output is correct
18	Correct	7 ms	9728 KB	Output is correct
19	Correct	10 ms	9728 KB	Output is correct
20	Correct	7 ms	9728 KB	Output is correct
21	Correct	9 ms	9728 KB	Output is correct
22	Correct	6 ms	9728 KB	Output is correct
23	Correct	8 ms	9728 KB	Output is correct
24	Correct	7 ms	9728 KB	Output is correct
25	Correct	8 ms	9728 KB	Output is correct
26	Correct	7 ms	9728 KB	Output is correct
27	Correct	8 ms	9728 KB	Output is correct
28	Correct	8 ms	9728 KB	Output is correct
29	Correct	7 ms	9728 KB	Output is correct
30	Correct	6 ms	9728 KB	Output is correct
31	Runtime error	19 ms	19456 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-

Submission #276815

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0 / 20.0

Subtask #3 0 / 20.0

Subtask #4 15.0 / 15.0

Subtask #5 0 / 20.0

Subtask #6 0 / 15.0

Subtask #1
10.0 / 10.0

Subtask #2
0 / 20.0

Subtask #3
0 / 20.0

Subtask #4
15.0 / 15.0

Subtask #5
0 / 20.0

Subtask #6
0 / 15.0