Submission #235657

#	Time	Username	Problem	Language	Result	Execution time	Memory
235657		triple_fault	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1110 ms	221968 KiB

shoes

#include "shoes.h"

#include <set>
#include <cstdio>
#include <algorithm>

#define ll long long
#define mid ((tl + tr) / 2)
#define lft (v * 2)
#define rht ((v * 2) + 1)
#define MAX 200000

using namespace std;

ll n;
vector<ll> shoes(MAX);

ll active_t[4 * MAX]; 

struct segtree {
    segtree* left = NULL; segtree* right = NULL;
    multiset<ll> here;
    ll m_tl, m_tr;

    void build(ll tl, ll tr) {
        m_tl = tl, m_tr = tr;

        if (tl == tr) {
            here.insert(shoes[tl]);
            return;
        }
        left = new segtree();
        right = new segtree();
        left->build(tl, mid);
        right->build(mid + 1, tr);

        merge(left->here.begin(), left->here.end(), right->here.begin(), right->here.end(),
                inserter(here, here.begin()));
    }

    ll query(ll needle) {
        here.erase(here.find(needle));
        if (m_tl == m_tr) return m_tl;

        if (left->here.find(needle) != left->here.end()) 
            return left->query(needle);
        else if (right->here.find(needle) != right->here.end())
            return right->query(needle);
        else puts("fuck this");
        return 696969696969696969;
    }
} segtree;

void build(ll v, ll tl, ll tr) {
    if (tl == tr) active_t[v] = 0;
    else {
         build(lft, tl, mid);
         build(rht, mid + 1, tr);
         active_t[v] = active_t[lft] + active_t[rht];
    }
}

void set_inactive(ll v, ll idx, ll tl, ll tr) {
    if (tl > tr) return;
    if (tl == tr) active_t[v] = 1;
    else {
        if (idx > mid) set_inactive(rht, idx, mid + 1, tr);
        else set_inactive(lft, idx, tl, mid);
        active_t[v] = active_t[lft] + active_t[rht];
    }
}

ll query(ll v, ll tl, ll tr, ll l, ll r) {
    if (l > r) return 0;
    if (l == tl && r == tr) return active_t[v];
    return query(lft, tl, mid, l, min(r, mid)) + 
        query(rht, mid + 1, tr, max(mid + 1, l), r);
}

long long count_swaps(std::vector<int> s) {
    ll n = s.size();
    for (ll i = 0; i < n; ++i) shoes[i] = (ll)s[i];

    segtree.build(0, n - 1);
    build(1, 0, n - 1);

    ll ans = 0;
    for (ll i = 0; i < n; ++i) {
        if (query(1, 0, n - 1, i, i) == 1) continue;

        segtree.query(shoes[i]);
        ll nxt = -shoes[i];

        ll q = segtree.query(nxt);
        ans += (q - i - 1 - query(1, 0, n - 1, i, q)); 
        if (nxt < 0) ++ans;

        set_inactive(1, i, 0, n - 1);
        set_inactive(1, q, 0, n - 1);
    }
	return ans;
}

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