Submission #235946

#	Time	Username	Problem	Language	Result	Execution time	Memory
235946		triple_fault	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1104 ms	226040 KiB

shoes

#include "shoes.h"

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

#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);

struct segtree {
    segtree* left = NULL; segtree* right = NULL;
    multiset<ll> here;
    ll m_tl, m_tr;
    bool inactive = true;
    ll sum_here = 0;

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

        if (tl == tr) {
            here.insert(shoes[tl]);
            inactive = false;
            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));
        ++sum_here;
        if (m_tl == m_tr) {
            inactive = true;
            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 MAX * MAX;
    }

    ll sum(ll tl, ll tr) {
        if (tl > tr) return 0;
        if (tl == m_tl && tr == m_tr) return sum_here;

        return left->sum(tl, min(tr, (m_tl + m_tr) / 2)) +
            right->sum(max(tl, ((m_tl + m_tr) / 2) + 1), tr);
    }

} segtree;

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);

    ll inactive_a[n];
    memset(inactive_a, 0, sizeof inactive_a);

    ll ans = 0;
    for (ll i = 0; i < n; ++i) {
        if (inactive_a[i]) continue;
        segtree.query(shoes[i]);
        ll nxt = -shoes[i];

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

        inactive_a[i] = 1; inactive_a[q] = 1;
    }
	return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'long long int segtree::query(long long int)':
shoes.cpp:56:20: warning: integer overflow in expression [-Woverflow]
         return MAX * MAX;
                    ^

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