Submission #1216934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216934		pensive	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	400 ms	178068 KiB

shoes

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define REP(a,i,n) for (ll i=a;i<n;i++)

map<ll, queue<ll> > saan;

struct SegTree {
    ll l, r, val;
    SegTree* lt, * rt;

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

    SegTree(ll left, ll right, vector<ll>& a) {
        l = left; r = right;
        lt = rt = nullptr;

        if (left==right) {
            val = a[left];
            return;
        }

        ll mid = (l+r)>>1;
        lt = new SegTree(l, mid, a);
        rt = new SegTree(mid+1, r, a);
        combine();
    }

    void update(ll i){
        if(l <= i && i <= r){
            if (lt) {
                lt->update(i);
                rt->update(i);
                combine();
            }
            else {
                val++;
            }
        }
    }

    ll query(ll ql, ll qr) {
        if (qr < l || r < ql) { // completely out
            return 0;
        }
        if ( ql <= l && r <= qr) { //completely in
            return val;
        }
        return lt->query(ql, qr) + rt->query(ql, qr);
    }
};


ll count_swaps(vector<int> S) {
    vector<ll> arr;
    ll N=S.size(), ind=0, count=0;
    for (auto shoe : S) {
        if (saan[shoe].empty()) {
            saan[-shoe].push(ind + (shoe < 0)); //push the opposite
            arr.push_back(ind + (shoe > 0));
            ind += 2;
        }
        else {
            arr.push_back(saan[shoe].front());
            saan[shoe].pop();
        }
    }
    vector<ll> ex(300'005, 0);
    SegTree* sgt = new SegTree(0, 300'004, ex);
    for (ll i=N-1; i>=0;i--) {
        count += sgt->query(0, arr[i]-1);
        sgt->update(arr[i]);
    }

    return count;
}

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