Submission #1016203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016203		BestCrazyNoob	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	102 ms	73820 KiB

shoes

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct SegTree {
    int sz;
    vector<int> tree;
    int ql, qr;
    void merge(int i) {
        tree[i] = tree[2*i]+tree[2*i+1];
    }
    SegTree(int N) {
        sz = 1;
        while (sz < N) sz *= 2;
        tree.resize(2*sz);
        for (int i = sz; i < sz+N; i++) tree[i] = 1;
        for (int i = sz+N; i < 2*sz; i++) tree[i] = 0;
        for (int i = sz-1; i >= 1; i--) merge(i);
    }
    int __query(int ni, int nl, int nr) {
        if (qr <= nl || nr <= ql) return 0;
        if (ql <= nl && nr <= qr) return tree[ni];
        int nm = (nl+nr)/2;
        return __query(2*ni, nl, nm) + __query(2*ni+1, nm, nr);
    }
    int query(int l, int r) {
        ql = l;
        qr = r;
        return __query(1, 0, sz);
    }
    void set0(int i) {
        i += sz;
        tree[i] = 0;
        for (i /= 2; i >= 1; i /= 2) {
            merge(i);
        }
    }
};

long long count_swaps(vector<int> S) {
    const int N = S.size() / 2;
    vector<queue<int>> queues(N+1); // Index where given numbers appear
    vector<int> other(2*N); // Index of other pair element
    for (int i = 0; i < 2*N; i++) {
        const int x = abs(S[i]);
        if (!queues[x].size() || S[queues[x].front()] == S[i]) {
            queues[x].push(i);
        } else {
            const int j = queues[x].front();
            queues[x].pop();
            other[i] = j;
            other[j] = i;
        }
    }
    SegTree seg(2*N);
    long long ans = 0;
    for (int i = 0; i < 2*N; i++) {
        if (other[i] < i) continue;
        if (S[i] > 0) ans++; // this is a right shoe, to be swapped at the end
        ans += seg.query(i+1, other[i]);
        seg.set0(i);
        seg.set0(other[i]);
    }
    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