Submission #1016291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016291		Ariadna	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	135 ms	141756 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long

using namespace std;

struct Segtree {
    int n;
    vector<int> st;

    Segtree(vector<int>& a) {
        n = (int)a.size();
        st = vector<int>(4*n);
        build(1, 0, n-1, a);
    }

    void build(int p, int l, int r, const vector<int>& a) {
        if (l == r) st[p] = a[l];
        else {
            int m = (l+r)/2;
            build(2*p, l, m, a);
            build(2*p+1, m+1, r, a);
            st[p] = st[2*p]+st[2*p+1];
        }
    }

    void change(int p, int l, int r, int i) {
        if (l == r) st[p] = 1-st[p];
        else {
            int m = (l+r)/2;
            if (i <= m) change(2*p, l, m, i);
            else change(2*p+1, m+1, r, i);
            st[p] = st[2*p]+st[2*p+1];
        }
    }

    int sum(int p, int l, int r, int i, int j) {
        if (i > j) return 0;
        if (l == i && r == j) return st[p];
        int m = (l+r)/2;
        return sum(2*p, l, m, i, min(m, j))+sum(2*p+1, m+1, r, max(i, m+1), j);
    }

    void change(int i) { change(1, 0, n-1, i); }
    int sum(int i, int j) { return sum(1, 0, n-1, i, j); }
};

ll count_swaps(vector<int> S) {
    ll ans = 0;
    int n = (int)S.size();

    vector<int> pair(n);
    vector<queue<int>> pos(n/2+1), neg(n/2+1);

    for (int i = n-1; i >= 0; --i) {
        if (S[i] > 0) {
            if (neg[S[i]].empty()) {
                pos[S[i]].push(i);
                pair[i] = -1;
            } else {
                pair[i] = neg[S[i]].front();
                neg[S[i]].pop();
            }
        } else {
            if (pos[-S[i]].empty()) {
                neg[-S[i]].push(i);
                pair[i] = -1;
            } else {
                pair[i] = pos[-S[i]].front();
                pos[-S[i]].pop();
            }
        }
    }

    vector<int> a(n, 1);
    Segtree St(a);

    for (int i = 0; i < n; ++i) {
        if (pair[i] == -1) continue;
        ans += St.sum(i+1, pair[i]-1);
        if (S[i] > 0) ++ans;
        St.change(i);
        St.change(pair[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