Submission #824991

#	Time	Username	Problem	Language	Result	Execution time	Memory
824991		phoenix	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	294 ms	26808 KiB

shoes

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

using namespace std;

const int N = (1 << 18);

int t[2 * N];
void update(int ql, int qr, int x) {
	if(ql > qr) return;
	for(ql += N, qr += N + 1; ql < qr; ql >>= 1, qr >>= 1) {
		if(ql & 1) t[ql++] += x;
		if(qr & 1) t[--qr] += x;
	}
}
int get(int pos) {
	int s = 0;
	for(pos += N; pos; pos >>= 1) 	
		s += t[pos];
	return s;
}

long long count_swaps(vector<int> s) {
	int n = (int)s.size();
	long long ans = 0;
	map<int, vector<int>> mp;

	for(int i = n - 1; i >= 0; i--) 	
		mp[s[i]].push_back(i);
	bool us[n] = {};
	for(int st = 0; st < n; st++) {
		if(us[st]) continue;
		int pos = mp[-s[st]].back();
		us[st] = 1;
		us[pos] = 1;
		mp[s[pos]].pop_back();
		mp[s[st]].pop_back();
		ans += pos + get(pos) - st - get(st) - 1;
		update(st + 1, pos - 1, +1);
		if(s[st] > 0) ans++;
	}	

	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