Submission #1216910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216910		pensive	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	217 ms	291628 KiB

shoes

#include<bits/stdc++.h>

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

vector<queue<int> > saan(400'005);

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

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

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

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

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

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

    int query(int ql, int 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);
    }
};


int count_swaps(vector<int> S) {
    vector<int> arr;
    int N=S.size(), ind=0, count=0;
    for (int shoe : S) {
        if (saan[shoe + 200'000].empty()) {
            saan[-shoe + 200'000].push(ind + (shoe < 0)); //push the opposite
            arr.push_back(ind + (shoe > 0));
            ind += 2;
        }
        else {
            arr.push_back(saan[shoe + 200'000].front());
            saan[shoe + 200'000].pop();
        }
    }
    vector<int> ex(ind, 0);
    SegTree* sgt = new SegTree(0, ind-1, ex);
    for (int 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: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15