Submission #867499

#	Time	Username	Problem	Language	Result	Execution time	Memory
867499		cheat_when_I_was_young	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	75 ms	75480 KiB

shoes

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

void update(int pos, int val, vector<int> &bit) {
    ++pos;
    for (; pos < (int)bit.size(); pos += pos&-pos)
        bit[pos] += val;
}

void range_update(int l, int r, int val, vector<int> &bit) {
    update(l, val, bit);
    update(r+1, -val, bit);
}

int get(int pos, vector<int> &bit) {
    ++pos;
    int res = 0;
    for (; pos > 0; pos -= pos&-pos)
        res += bit[pos];
    return res;
}

long long count_swaps(vector<int> s) {
    int n = (int)s.size();
    long long ans = 0;
    vector<int> bit(n+1, 0);
    vector<vector<int>> l(n/2+1, vector<int>());
    vector<queue<int>> r(n/2+1, queue<int>());

    for (int i = 0; i < n; ++i) {
        if (s[i] < 0) {
            s[i] = -s[i];
            if (r[s[i]].size()) {
                ans += i - r[s[i]].front() - get(r[s[i]].front(), bit);
                range_update(r[s[i]].front(), i, 1, bit);
                r[s[i]].pop();
            } else
                l[s[i]].push_back(i);
        } else {
            if (l[s[i]].size()) {
                ans += i - l[s[i]].back() - get(l[s[i]].back(), bit) - 1;
                range_update(l[s[i]].front(), i, 1, bit);
                l[s[i]].pop_back();
            } else
                r[s[i]].push(i);
        }
    }

    return ans;
}

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