Submission #438882

#	Time	Username	Problem	Language	Result	Execution time	Memory
438882		vkgainz	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	344 ms	274988 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define int64 int64_t

struct seg_tree {
    vector<int> seg;
    int sz;
    void init(int N) {
        sz = 1;
        while(sz < N) sz *= 2;
        seg.resize(2 * sz);
    }
    void upd(int i, int x, int lx, int rx) {
        if(rx - lx == 1) {
            seg[x] = 1;
            return;
        }
        int m = (lx + rx) / 2;
        if(i < m) upd(i, 2 * x + 1, lx, m);
        else upd(i, 2 * x + 2, m, rx);
        seg[x] = seg[2 * x + 1] + seg[2 * x + 2];
    }
    void upd(int i) { upd(i, 0, 0, sz); }
    int query(int l, int r, int x, int lx, int rx) {
        if(lx >= r || rx <= l) return 0;
        if(lx >= l && rx <= r) return seg[x];
        int m = (lx + rx) / 2;
        return query(l, r, 2 * x + 1, lx, m) + query(l, r, 2 * x + 2, m, rx);
    }
    int query(int l, int r) { return query(l, r, 0, 0, sz); }
} in;

int64 count_swaps(vector<int> S) {
    int64 ans = 0;
    int N = (int) S.size();
    in.init(N + 1);
    vector<deque<int>> l(N + 1), r(N + 1);
    for(int i = 0; i < N; i++) {
        if(S[i] < 0) {
            if(!r[-S[i]].empty()) {
                ans += in.query(r[-S[i]].front(), i) + 1;
                in.upd(r[-S[i]].front());
                in.upd(i);
                r[-S[i]].pop_front();
            }
            else 
                l[-S[i]].push_back(i);
        }
        else {
            if(!l[S[i]].empty()) {
                ans += in.query(l[S[i]].front(), i);
                in.upd(l[S[i]].front());
                in.upd(i);
                l[S[i]].pop_front();
            }
            else
                r[S[i]].push_back(i);
        }
    }
    return ans;
}

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