Submission #987616

#	Time	Username	Problem	Language	Result	Execution time	Memory
987616		Tsagana	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	258 ms	278448 KiB

shoes

#include "shoes.h"

#include<bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second

#define meta int M = (L + R) / 2, x = 2 * id, y = x + 1

using namespace std;

queue<int> q[400001];
int res[400001];
int dp[400001];
 
struct Tree{
	int tree[1600001];
	void update(int id, int L, int R, int i){
		if (L == R) {tree[id] = 1; return ;}
		meta;
		if (L <= i && i <= M) update(x, L, M, i);
		else update(y, M + 1, R, i);
		tree[id] = tree[x] + tree[y];
	}
	int query(int id, int l, int r, int L, int R) {
		if (l <= L && R <= r) return tree[id];
		if (l >  R || L >  r) return 0;
		meta;
		return query(x, l, r, L, M) + query(y, l, r, M + 1, R);
	}
} T;
 
long long count_swaps(vector<int> v) {
	int n = v.size(), num = n;
	for (int i = n-1; i >= 0; i--) {
		if (q[v[i] + n].empty()) {
			if (v[i] > 0) {res[i+1] = num; q[n-v[i]].push(num-1);}
			else {res[i+1] = num-1; q[n-v[i]].push(num);}
			num -= 2;
		}
		else {res[i+1] = q[v[i]+n].front(); q[v[i]+n].pop();}
	}
	long long resp = 0;
	for (int i = 1; i <= n; i++){
		resp += T.query(1, res[i], n, 1, n);
		T.update(1, 1, n, res[i]);
	}
	return resp;
}

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