Submission #217051

#	Time	Username	Problem	Language	Result	Execution time	Memory
217051		thatprogrammer	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	154 ms	22780 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100002;
int ft[2 * MAXN];
void update(int x, int v, int N) {
    while (x <= N) {
        ft[x] += v;
        x += (x & -x);
    }
}
int query(int x) { return x > 0 ? ft[x] + query(x - (x & -x)) : 0; }
// One indexed
long long count_swaps(vector<int> s) {
    set<int> nums[MAXN * 2];
    int n = s.size() / 2;
    for (int i = 0; i < 2 * n; i++) nums[s[i] + n].insert(i);
    ll ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        int cur = *(nums[s[i] + n].begin());
        if (cur != i) continue;
        int j = *(nums[-s[i] + n].begin());
        nums[-s[i] + n].erase(nums[-s[i] + n].begin());
        nums[s[i] + n].erase(nums[s[i] + n].begin());
        int tot = query(2 * n + 1);
        // cout << j << " " << tot << endl;
        int newI = cur + tot - query(i + 1);
        int newJ = j + tot - query(j + 1);
        // cout << i << " " << newI << " " << newJ << endl;
        if (s[i] < 0)
            ans += newJ - newI - 1;
        else
            ans += newJ - newI;
        update(j + 1, 1, MAXN * 2);
    }
    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