Submission #1016200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016200		BestCrazyNoob	Arranging Shoes (IOI19_shoes)	C++17	15 / 100	14 ms	3164 KiB

shoes

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct SegTree {
    int sz;
    vector<int> tree;
    int ql, qr;
    void merge(int i) {
        tree[i] = tree[2*i]+tree[2*i+1];
    }
    SegTree(int N) {
        sz = 1;
        while (sz < N) sz *= 2;
        tree.resize(2*sz);
        for (int i = sz; i < sz+N; i++) tree[i] = 1;
        for (int i = sz+N; i < 2*sz; i++) tree[i] = 0;
        for (int i = sz-1; i >= 1; i--) merge(i);
    }
    int __query(int ni, int nl, int nr) {
        if (qr <= nl || nr <= ql) return 0;
        if (ql <= nl && nr <= qr) return tree[ni];
        int nm = (nl+nr)/2;
        return __query(2*ni, nl, nm) + __query(2*ni+1, nm, nr);
    }
    int query(int l, int r) {
        ql = l;
        qr = r;
        return __query(1, 0, sz);
    }
    void set0(int i) {
        i += sz;
        tree[i] = 0;
        for (i /= 2; i >= 1; i /= 2) {
            merge(i);
        }
    }
};

long long count_swaps(vector<int> S) {
    const int N = S.size() / 2;
    return N*(long long)(N-1)/2;
}

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