Submission #941432

#	Time	Username	Problem	Language	Result	Execution time	Memory
941432		Programmer123	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	291 ms	92756 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

struct node {
    int min, max;
    node *left, *right;
    int value;

    node(int l, int r) {
        min = l;
        max = r;
        if (r == l + 1) {
            left = right = nullptr;
        } else {
            left = new node(l, (l + r) / 2);
            right = new node((l + r) / 2, r);
        }
        value = max - min;
    }

    void erase(int x) {
        if (x < min || x >= max) return;
        value--;
        if (x == min && x + 1 == max) return;
        left->erase(x);
        right->erase(x);
    }

    int query(int l, int r) const {
        l = std::max(l, min);
        r = std::min(r, max);
        if (l >= r) return 0;
        if (l >= max || r <= min) return 0;
        if (l == min && r == max) return value;
        return left->query(l, r) + right->query(l, r);
    }
};

long long count_swaps(std::vector<int> s) {
    int N = s.size() / 2;
    node tree(0, 2 * N);
    long long ans = 0;
    auto moveLeft = [&](int idx) {
        ans += tree.query(0, idx);
        tree.erase(idx);
    };
    std::map<int, std::queue<int>> rights;
    for (int i = 0; i < 2 * N; ++i) {
        if (s[i] > 0) {
            rights[s[i]].push(i);
        }
    }
    for (int i = 0; i < 2 * N; ++i) {
        if (s[i] < 0) {
            assert(!rights[-s[i]].empty());
            int x = rights[-s[i]].front();
            rights[-s[i]].pop();
            moveLeft(i);
            moveLeft(x);
        }
    }
    assert(tree.value == 0);
    for (auto [a, b]: rights) {
        assert(b.empty());
    }
    return ans;
}

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