Submission #961874

#	Time	Username	Problem	Language	Result	Execution time	Memory
961874		Gr1sen	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	295 ms	276492 KiB

shoes

#include "shoes.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>

using namespace std;

#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<stack<int>>

struct segmentTree {
	int n;
	vi L;
	void set_n(int a) {
		n = a;
		L.resize(4*n, 0);
	}
	void update(int p, int l, int r, int x, int v) {
		if (l > x || r < x) return;
		if (l == r) {
			L[p] = v;
			return;
		}
		int m = (l+r)/2;
		update(p*2, l, m, x, v);
		update(p*2+1, m+1, r, x, v);
		L[p] = L[p*2] + L[p*2+1];
	}
	int query(int p, int l, int r, int x, int y) {
		//cerr << p << " " << l << " " << r << " " << x << " " << y << endl;
		if (l > y || r < x) return 0;
		if (x <= l && r <= y) {
			return L[p];
		}
		int m = (l+r)/2;
		return query(p*2, l, m, x, y) + query(p*2+1, m+1, r, x, y);
	}
	void print() {
		for (auto i : L) {
			cerr << i << " ";
		}
		cerr << endl;
	}
};

ll count_swaps(vector<int> S) {
	//cerr << endl;
	int n = S.size();
	vs L(n*2+5);
	for (int i = n-1; i > -1; i--) L[S[i]+n].push(i);
	segmentTree T;
	T.set_n(n+5);
	ll t = 0;
	int p = 0;
	while (p < n) {
		//cerr << p << " " << t << endl;
		if (T.query(1, 0, n, p, p)) {
			//cerr << "oink" << endl;
			p++; continue;
		}
		L[S[p]+n].pop();
		//T.print();
		//cerr << "oink" << endl;
		int a = L[S[p]*(-1)+n].top();
		L[S[p]*(-1)+n].pop();
		//cerr << "oink" << endl;
		t += a-p-T.query(1, 0, n, p, a);
		//cerr << "oink" << endl;
		if (S[p] < 0) t--;
		T.update(1, 0, n, a, 1);
		p++;
	}
	return t;
}

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