Submission #711909

#	Time	Username	Problem	Language	Result	Execution time	Memory
711909		thimote75	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	116 ms	7864 KiB

shoes

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

using namespace std;

#define num long long
#define idata vector<int>
#define di pair<int, int>

struct PosM {
    set<di> u;

    void insert (int type, int pos) {
        u.insert({ type, pos });
    }
    int find (int type) {
        di data = *u.lower_bound({ type, -1 });
        u.erase(data);

        return data.second;
    }
};

PosM pos_query;

struct SegTree {
    vector<int> tree;

    int size, start, height;

    SegTree (int ps) {
        size = ps;
        height = ceil(log2(ps));
        start = 1 << height;

        tree.resize(start << 1);
    }
    void update (int l, int r, int delta) {
        l += start;
        r += start;

        while (l < r) {
            if ((l & 1) == 1) tree[l] += delta;
            if ((r & 1) == 0) tree[r] += delta;

            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) tree[l] += delta;
    }
    int query (int index) {
        int res = 0;

        index += start;
        while (index != 0) {
            res += tree[index];
            index >>= 1;
        }

        return res;
    }
};

long long count_swaps (idata shoe_array) {
    int nbShoes = shoe_array.size();

    vector<di> displacements;

    for (int idShoe = 0; idShoe < nbShoes; idShoe ++) {
        if (shoe_array[idShoe] > 0)
            pos_query.insert(shoe_array[idShoe], idShoe);
    }

    num answer = 0;

    for (int idShoe = 0; idShoe < nbShoes; idShoe ++) {
        if (shoe_array[idShoe] < 0) {
            int q = pos_query.find( - shoe_array[idShoe] );

            if (q < idShoe) answer ++;
            displacements.push_back({ min(idShoe, q), max(idShoe, q) });
        }
    }

    SegTree tree(nbShoes);

    for (di displ : displacements) {
        int x  = displ.first;
        int y  = displ.second;
        int rx = x + tree.query(x);
        int ry = y + tree.query(y);

        answer += ry - rx - 1;
        tree.update(x, y, 1);
    }

    return answer;
}

/*int main () {
    int nbNodes;
    cin >> nbNodes;

    idata s;
    for (int i = 0; i < nbNodes; i ++) {
        int x;
        cin >> x;

        s.push_back(x);
    }

    cout << count_swaps(s);
}*/

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