Submission #361516

#	Time	Username	Problem	Language	Result	Execution time	Memory
361516		maximrufed	Arranging Shoes (IOI19_shoes)	C++14	30 / 100	350 ms	26732 KiB

shoes

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define pii pair<int, int>

using namespace std;

struct segtree {
    int n;
    vector<int> tree;

    void build(int v, int l, int r) {
        if (l + 1 == r) {
            tree[v] = 1;
            return;
        }
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
        tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
    }

    segtree() {}
    segtree(int nn) {
        n = nn;
        tree.assign(n * 4, 0);
        build(0, 0, n);
    }

    int get(int v, int tl, int tr, int l, int r) {
        if (l <= tl && tr <= r) return tree[v];
        if (tr <= l || r <= tl) return 0;
        int tm = (tl + tr) / 2;
        return get(v * 2 + 1, tl, tm, l, r) + get(v * 2 + 2, tm, tr, l, r);
    }

    int get(int l, int r) {
        return get(0, 0, n, l, r + 1);
    }

    void set(int v, int l, int r, int p) {
        if (l + 1 == r) {
            tree[v] = 0;
            return;
        }
        int m = (l + r) / 2;
        if (p < m) {
            set(v * 2 + 1, l, m, p);
        } else {
            set(v * 2 + 2, m, r, p);
        }
        tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
    }

    void set(int p) {
        set(0, 0, n, p);
    }
};

vector<vector<int>> b;
map<int, int> pos;

int get(int x) {
    int ans = b[pos[x]].back();
    b[pos[x]].pop_back();
    return ans;
}

ll count_swaps(vector<int> a) {
    int n = a.size() / 2;
    segtree tree = segtree(n * 2);
    int ans = 0;

    int nxt = 0;
    pos.clear();
    for (auto e : a) {
        if (pos.find(e) == pos.end()) {
            pos[e] = nxt++;
        }
    }

    b.assign(nxt, vector<int>(0, 0));
    for (int i = n * 2 - 1; i >= 0; i--) {
        b[pos[a[i]]].pb(i);
    }

    for (int i = 0; i < n * 2; i++) {
        if (tree.get(i, i) == 0) continue;
        int l = i, r = get(-a[i]);
        tree.set(l);
        tree.set(r);
        ans += tree.get(l, r) + (bool) (a[i] > 0);
    }
    return ans;
}

// signed main() {
//  ios::sync_with_stdio(0);
//  cin.tie(0);
//  cout.tie(0);
//  cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl;
//  return 0;
// }

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