Submission #1211729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211729		ProtonDecay314	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	385 ms	49728 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;

// Range sum point update segtree
struct Tree {
    Tree *lt, *rt;
    int l, r;
    int v;

    Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(0) {};

    void combine() {
        v = lt->v + rt->v;
    }

    void build(const vi& a) {
        if(l == r) {
            v = a[l];
            return;
        }

        int m = (l + r) >> 1;

        lt = new Tree(l, m);
        rt = new Tree(m + 1, r);
        lt->build(a);
        rt->build(a);

        combine();
    }

    int qry(int ql, int qr) {
        if(ql > r || qr < l) return 0;

        if(ql == l && qr == r) return v;

        int m = (l + r) >> 1;

        return lt->qry(ql, min(qr, m)) + rt->qry(max(ql, m + 1), qr);
    }

    void upd(int i, int nv) {
        if(i > r || i < l) return;

        if(l == r) {
            v = nv;
            return;
        }

        int m = (l + r) >> 1;

        if(i <= m) lt->upd(i, nv);
        else rt->upd(i, nv);

        combine();
    }
};

ll count_swaps(vi s) {
    int n = s.size();
    vi init_tree_vals(n, 1);
    Tree tr(0, n - 1);
    tr.build(init_tree_vals);

    // store the indices at which each size occurs
    typedef map<int, set<int>> map_set;
    map_set pos;
    
    for(int i = 0; i < n; i++) {
        if(pos.count(s[i]) == 0) {
            // Create a new entry
            pos[s[i]] = set<int>();
        }
        pos[s[i]].insert(i);
    }
    
    ll num_swaps = 0ll;
    
    // greedily match the shoes
    for(int i = 0; i < n; i++) {
        if(tr.qry(i, i) == 0) continue;
        
        if(s[i] > 0) num_swaps++;
        
        int other_pos = *pos[-s[i]].begin();
        
        int num_intermediate = tr.qry(i + 1, other_pos - 1);
        
        num_swaps += (ll)num_intermediate;
        
        tr.upd(i, 0);
        tr.upd(other_pos, 0);
        pos[s[i]].erase(i);
        pos[-s[i]].erase(other_pos);
    }

	return num_swaps;
}

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