Submission #414659

#	Time	Username	Problem	Language	Result	Execution time	Memory
414659		hibye1217	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	231 ms	81592 KiB

shoes

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

typedef long long ll;
typedef pair<int, int> pii;
#define fr first
#define sc second

set<int> cs; map<int, int> cc;
queue<pii> q[100020];
vector<pii> v;

const int N = 262144;
int tree[262150];

void upd(int pos, int val){ pos += 1;
	for (int i = pos; i < N; i += i&-i){ tree[i] += val; }
}

int qry(int pos){ pos += 1;
	int res = 0;
	for (int i = pos; i > 0; i -= i&-i){ res += tree[i]; }
	return res;
}

long long count_swaps(std::vector<int> s) {
	int n = s.size();
	for (int i = 0; i < n; i++){
		if (s[i] > 0){ cs.insert(s[i]); }
	}
	int c = 0;
	for (int x : cs){
		c += 1;
		cc[x] = c;
	}
	for (int i = 0; i < n; i++){
		if (s[i] > 0){ s[i] = cc[ s[i] ]; }
		else{ s[i] = -cc[ -s[i] ]; }
	}
	for (int i = 0; i < n; i++){
		int idx = abs(s[i]);
		//cout << "Q " << i << ' ' << s[i] << ' ';
		if (q[idx].empty()){ q[idx].push({s[i], i}); /* cout << "PSH" << endl; */ }
		else if (q[idx].front().fr == s[i]){ q[idx].push({s[i], i}); /* cout << "PSH" << endl; */ }
		else{
			v.push_back({ q[idx].front().sc, i }); /* cout << "PAIR " << q[idx].front().sc << ' ' << i << endl; */
			q[idx].pop();
		}
	}
	sort(v.begin(), v.end());
	ll ans = 0;
	for (int i = 0; i < n; i++){ upd(i, 1); }
	for (pii p : v){
		int i1 = p.fr, i2 = p.sc;
		//cout << "P " << i1 << ' ' << i2 << endl;
		ans += qry(i2) - qry(i1) - 1;
		//cout << "QRY " << qry(i1) << ' ' << qry(i2) << endl;
		if (s[i1] > s[i2]){ ans += 1; }
		upd(i1, -1); upd(i2, -1);
	}
	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