Submission #986571

#	Time	Username	Problem	Language	Result	Execution time	Memory
986571		mariaclara	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	79 ms	73236 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, bit[MAXN];

void update(int x, int val) {
	for( ; x < 2*n; x += x&-x)
		bit[x] += val;
}

int query(int x) {
	int cnt = 0;
	while(x > 0) {
		cnt += bit[x];
		x -= x&-x;
	}
	return cnt;
}
ll count_swaps(vector<int> s) {
	
	n = sz(s)/2;
	vector<int> pos(2*n,0);
	vector<pii> v;
	vector<queue<int>> fila(n+1);

	ll ans = 0;
	for(int i = 2*n-1; i >= 0; i--) {
		int x = abs(s[i]);
		if(fila[x].empty()) { 
			fila[x].push(i);
		}
		else if(s[fila[x].front()] != s[i]) {
			v.pb({i, fila[x].front()});
			if(s[i] > 0) ans++;
			pos[fila[x].front()] = pos[i] = sz(v)-1;
			fila[x].pop();
		}
		else fila[x].push(i);
	}

	for(int i = 0; i < 2*n; i++) {
		auto [l,r] = v[pos[i]];
		if(l == i) {
			update(r, 1);
			ans += (query(2*n-1) - query(r));
		}
		else {
			update(r, -1);
			ans += (query(2*n-1) - query(r));
		}
	}

	return ans;
}

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