Submission #395502

#	Time	Username	Problem	Language	Result	Execution time	Memory
395502		luisgalan	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	364 ms	278620 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long int ll;
const int MAX_N = ll(2e5 + 3);

ll st[4 * MAX_N];

void build(int p, int tl, int tr) {
    if (tl == tr) {
        st[p] = 0;
        return;
    }
    int m = (tl + tr) / 2;
    build(2*p, tl, m);
    build(2*p+1, m+1, tr);
    st[p] = st[2*p] + st[2*p+1];
}

ll query(int p, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return st[p];
    }
    int m = (tl + tr) / 2;
    ll L = query(2*p, tl, m, l, min(r, m));
    ll R = query(2*p+1, m+1, tr, max(l, m+1), r);
    return L + R;
}

void update(int p, int tl, int tr, int k, ll v) {
    if (tl == tr) {
        st[p] = v;
        return;
    }
    int m = (tl + tr) / 2;
    if (k <= m) {
        update(2*p, tl, m, k, v);
    } else {
        update(2*p+1, m+1, tr, k, v);
    }
    st[p] = st[2*p] + st[2*p+1];
}

ll count_swaps(vector<int> s) {
    int n = s.size();
    vector<int> taken(n);

    vector<queue<int>> neg(n + 1);
    vector<queue<int>> pos(n + 1);
    vector<int> pairs(n);

    // make pairs
    for (int i = 0; i < n; i++) {
        if (s[i] < 0) {
            if (!pos[-s[i]].empty()) {
                pairs[pos[-s[i]].front()] = i;
                pos[-s[i]].pop();
            } else {
                neg[-s[i]].push(i);
            }
        } else {
            if (!neg[s[i]].empty()) {
                pairs[neg[s[i]].front()] = i;
                neg[s[i]].pop();
            } else {
                pos[s[i]].push(i);
            }
        }
    }

    build(1, 0, n-1);

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (taken[i]) continue;
        int j = pairs[i];
        ans += j - i - query(1, 0, n-1, i, j);
        if (s[i] < 0) ans--;
        taken[i] = true;
        taken[j] = true;
        update(1, 0, n-1, i, taken[i]);
        update(1, 0, n-1, j, taken[j]);
    }
    return ans;
}

// queue for each shoe size
// use queue to find best pairs
// use something like a segtree to find number of swaps for each pair

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