Submission #1258941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258941		kawhiet	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	137 ms	33200 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

int n;
vector<int> st;

void build(int id, int tl, int tr) {
    if (tl == tr) {
        st[id] = 1;
        return;
    }
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    build(x, tl, tm);
    build(y, tm + 1, tr);
    st[id] = st[x] + st[y];
}

void update(int id, int tl, int tr, int i) {
    if (tl == tr) {
        st[id] = 0;
        return;
    }
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    if (i <= tm)
        update(x, tl, tm, i);
    else
        update(y, tm + 1, tr, i);
    st[id] = st[x] + st[y];
}

int query(int id, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return 0;
    if (l <= tl && tr <= r) return st[id];
    int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
    return query(x, tl, tm, l, r) + query(y, tm + 1, tr, l, r);
}

void update(int i) {
    update(0, 0, n - 1, i);
}

int query(int l, int r) {
    return query(0, 0, n - 1, l, r);
}

long long count_swaps(vector<int> a) {
    n = a.size();
    st.resize(4 * n);
    build(0, 0, n - 1);
    vector<set<int>> A(n + 1), B(n + 1);
    for (int i = 0; i < n; i++) {
        int x = abs(a[i]);
        if (a[i] > 0) {
            A[x].insert(i);
        }
        else {
            B[x].insert(i);
        }
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
        if (query(i, i) == 0) continue;
        int x = abs(a[i]);
        int id = 0;
        if (a[i] < 0) {
            id = *A[x].upper_bound(i);
            B[x].erase(i);
            A[x].erase(id);
        }
        else {
            id = *B[x].upper_bound(i);
            A[x].erase(i);
            B[x].erase(id);
        }
        update(i);
        update(id);
        res += query(i, id) + (a[i] > 0);
    }
    return res;
}

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