Submission #395483

#	Time	Username	Problem	Language	Result	Execution time	Memory
395483		luisgalan	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	487 ms	561612 KiB

shoes

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

ll st[4 * MAX_N];

void build(ll p, ll tl, ll tr) {
    if (tl == tr) {
        st[p] = 0;
        return;
    }
    ll 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(ll p, ll tl, ll tr, ll l, ll r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return st[p];
    }
    ll 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(ll p, ll tl, ll tr, ll k, ll v) {
    if (tl == tr) {
        st[p] = v;
        return;
    }
    ll 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) {
    ll n = s.size();
    vector<ll> taken(n);

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

    // make pairs
    for (ll 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 (ll i = 0; i < n; i++) {
        if (taken[i]) continue;
        ll 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: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15