Submission #154319

#	Time	Username	Problem	Language	Result	Execution time	Memory
154319		arman_ferdous	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	131 ms	21228 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 2e5+100;

ll bit[N];
void upd(int pos, ll x) {
	while(pos < N) bit[pos] += x, pos += pos&-pos;
}
ll pref(int pos, ll r = 0) {
	while(pos > 0) r += bit[pos], pos -= pos&-pos;
	return r;
}
ll get(int l, int r) {
	if(r < l) return 0;
	return pref(r) - pref(l - 1);
}

vector<int> le[N], ri[N]; int ryt[N];
long long count_swaps(vector<int> s) {
	int n = s.size();
	s.insert(s.begin(), 0);

	for(int i = 1; i <= n; i++) {
		ryt[i] = -1;
		upd(i, +1);
		if(s[i] < 0) le[-s[i]].push_back(i);
		else ri[s[i]].push_back(i);
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < (int)le[i].size(); j++) {
			int a = le[i][j], b = ri[i][j];
			ryt[min(a, b)] = max(a, b);
		}
	}

	ll ret = 0;
	for(int i = 1; i <= n; i++) if(ryt[i] + 1) {
		ret += get(i + 1, ryt[i] - 1);
		ret += (s[ryt[i]] < 0);
		upd(ryt[i], -1);
	}
	return ret;
}

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