Submission #1230298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230298		sethod	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	350 ms	26736 KiB

shoes

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

int st[525000];

void add(int x, int xl, int xr, int p){
    if(xl == xr){
        if(xl == p) st[x]++;
        return;
    }
    int mid = (xl + xr) / 2;
    if(p <= mid) add(x * 2 + 1, xl, mid, p);
    else add(x * 2 + 2, mid + 1, xr, p);
    st[x] = st[x * 2 + 1] + st[x * 2 + 2];
    return;
}
int sum(int x, int xl, int xr, int l, int r){
    if(xl >= l && xr <= r) return st[x];
    if(xr < l || xl > r) return 0;
    int mid = (xl + xr) / 2;
    return sum(x * 2 + 1, xl, mid, l, r) + sum(x * 2 + 2, mid + 1, xr, l, r);
}

long long count_swaps(vector<int> s) {
    int n = s.size()/2;
	map<int, priority_queue<int, vector<int>, greater<int>>> r, l;
	for(int i = 0; i < 2 * n; i++){
        if(s[i] > 0){
            r[s[i]].push(i);
        }else{
            l[abs(s[i])].push(i);
        }
	}
	vector<int> udh(2 * n, 0);
	long long ans = 0;
	for(int i = 0; i < 2*n; i++){
        if(!udh[i]){
            int pos;
            if(s[i] > 0) pos = l[s[i]].top();
            else pos=r[abs(s[i])].top();
            l[abs(s[i])].pop();
            r[abs(s[i])].pop();
            ans += abs(i - pos) - 1;
            ans -= sum(0, 0, 2 * n - 1, i + 1, pos);
            if(s[i] > 0) ans++;
            udh[pos] = 1;
            add(0, 0, 2 * n - 1, pos);
        }
	}
	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