Submission #744002

#	Time	Username	Problem	Language	Result	Execution time	Memory
744002		drdilyor	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	286 ms	46428 KiB

shoes

#include <bits/stdc++.h>
#ifdef ONPC
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
using namespace std;
//namespace pbds = __gnu_pbds;
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.first >> p.second; }
template<typename Cont> int sz(const Cont& cont) { return int(cont.size()); }
const string fileio = "";
constexpr int tests = 1, nmax = 2e5, nlog = __lg(nmax), mod = 1e9+7;

int nextPower2(int n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return 1+n;
}

struct segtree {
    int n;
    vector<vector<int>> t;
    segtree(vector<int>& arr) :n(nextPower2(arr.size())), t(n*2) {
        for (int i = 0; i < sz(arr); i++) {
            t[i+n].push_back(arr[i]);
        }
        for (int i = n-1; i; i--) {
            merge(t[i*2].begin(), t[i*2].end(),
                  t[i*2+1].begin(), t[i*2+1].end(),
                  back_inserter(t[i]));
        }
    }
    int query(int l, int r, int x, int v, int tl, int tr) {
        if (r < tl || tr < l || tr < tl) return 0;
        if (l <= tl && tr <= r) {
            return upper_bound(t[v].begin(), t[v].end(), x) - t[v].begin();
        }
        int mid = (tl+tr) / 2;
        return query(l, r, x, v*2, tl, mid) + query(l, r, x, v*2+1, mid+1, tr);
    };
    int query(int l, int r, int x) {
        return query(l, r, x, 1, 0, n-1);
    }
};

long long count_swaps(std::vector<int> s) {
    int n = s.size()/2;
    vector<int> pr(2*n, -1);
    vector<vector<int>> ix(n+1);
    for (int i = 0; i <n+n; i++)
        if (s[i] > 0)
            ix[s[i]].push_back(i);
    for (auto& i : ix) reverse(i.begin(), i.end());

    for (int i = 0; i < n+n; i++) {
        if (s[i] > 0) continue;
        int j = ix[-s[i]].back();
        ix[-s[i]].pop_back();
        pr[i] = j;
        pr[j] = i;
    }

    segtree st(pr);

    ll res = 0;
    for (int i = 0; i < n+n; i++) {
        if (s[i] > 0) continue;
        int a = i, b = pr[i];
        if (a > b) swap(a, b),res++;
        res += st.query(a+1, b-1, b);
    }
    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