Submission #1309563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309563		sano	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	870 ms	37460 KiB

shoes

#include <vector>
#include "shoes.h"
#include <iostream>
#define vec vector
#define ll long long
#define For(i, n) for(int i = 0; i < n; i++)

using namespace std;

class intervalac{
	int n;
	vec<int> l, r, in;
	void update(int s){
		in[s] = in[s*2] + in[s*2 + 1];
		return;
	}
public:
	intervalac(int vel){
		n = 1;
		while(n < vel) n*= 2;
		l.resize(2*n); r.resize(2*n); in.resize(2*n, 0);
		For(i, n){
			l[i+n] = r[i+n] = i;
		}
		for(int i = n-1; i >= 1; i--){
			l[i] = l[i*2];
			r[i] = r[i*2 + 1];
		}
		return;
	}
	int daj(int a, int b, int s = 1){
		if(l[s] > b || r[s] < a) return 0;
		if(a <= l[s] && r[s] <= b) return in[s];
		return daj(a, b, s*2) + daj(a, b, s*2 + 1);
	}
	void zmen(int a, int b){
		a+=n;
		in[a] += b;
		a/=2;
		while(a){
			update(a);
			a/=2;
		}
		return;
	}
};

long long count_swaps(std::vector<int> s) {
	
	int n = s.size();
	intervalac seg(n);
	vec<vec<int>> p(2*n), m(2*n);
	For(i, n){
		if(s[i] > 0) p[s[i]].push_back(i);
		else m[s[i] * (-1)].push_back(i);
	}
	int cnt = 0;
	ll vys = 0;
	vec<int> d(2*n, -1);
	For(i, 2*n){
		For(j, p[i].size()){
			//sparujeme p[i][j] a m[i][j]
			if(m[i][j] > p[i][j]) vys++;
			d[max(m[i][j], p[i][j])] = min(m[i][j], p[i][j]);
			s[p[i][j]] = s[m[i][j]] = cnt;
			cnt++;
		}
	}
	For(i, s.size()) cerr << s[i] << ' ';
	cerr << endl;
	For(i, d.size()) cerr << d[i] << ' ';
	cerr << endl;
	For(i, n){
		if(d[i] == -1) continue;
		vys += seg.daj(d[i], i);
		seg.zmen(i, 1);
		seg.zmen(d[i], 1);
	}
	return vys;
}

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