Submission #920021

#	Time	Username	Problem	Language	Result	Execution time	Memory
920021		tanprodium	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	50 ms	15768 KiB

shoes

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

using namespace std;

// random
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// templates
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (y > x) {
            x = y;
            return (true);
        } else return (false);
    }

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (y < x) {
            x = y;
            return (true);
        } else return (false);
    }

// define
#define fi    first
#define se    second

#define pub   push_back
#define pob   pop_back
#define puf   push_front
#define pof   pop_front
#define eb    emplace_back
#define upb   upper_bound
#define lwb   lower_bound

#define left  VAN
#define right TAN

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).begin(),(a).end()
#define sort_and_unique(a) sort(all(a));(a).resize(unique(all(a))-a.begin())
#define max_ max_element
#define min_ min_element

// another define
using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

// limit
const int oo = 2e9;

// function
void yesno(bool x) {
    cout << (x ? "YES\n" : "NO\n");
}

// structs
// FenwickTree
struct FenwickTree {
    vector<ll> ft;
    int from, to;

    FenwickTree() {}
    FenwickTree(int _from, int _to): from(_from), to(_to) {
        // set initial value

        ft.assign(to - from + 5, 0);
    }

private:
    void Upd(int p, ll v) {
        p = max(p, from);
        for (int j = p; j <= to; j += (j & (-j)))
            ft[j] += v;
    }

    ll Get(int p) {
        ll result = 0;
        p = min(p, to);
        for (int j = p; j >= from; j -= (j & (-j)))
            result += ft[j];
        return (result);
    }

public:
    void upd(int p, ll v) {
        Upd(p, v);
    }

    ll get(int p) {
        return (Get(p));
    }
};

ll count_swaps(vector<int> a) {
    int n = (int)a.size() / 2;
    ll ans = 0;
    vector<vector<int>> p(2 * n + 5);
    for (int i = 2 * n - 1; i >= 0; i--) {
        p[n + a[i]].push_back(i + 1);
        //cout << a[i] << ' ' << n + a[i] << '\n';
    }
    FenwickTree ft(1, 2 * n);
    for (int i = 0; i < 2 * n; i++) {
        bool ok = false;
        if ((int)p[n + a[i]].size()) {
            //cout << i << ' ' << a[i] << ' ' << p[n + a[i]].back() << '\n';
            if (p[n + a[i]].back() == i + 1) {
                ok = true;
            }
        }
        if (ok) {
            p[a[i] + n].pop_back();
            int l = i + 1;
            //cout << a[i] << '\n';
            int r = p[-a[i] + n].back();
            p[-a[i] + n].pop_back();
            if (a[i] < 0) {
                ans += r - l - 1 - ft.get(r) + ft.get(l - 1);
            } else {
                ans += r - l - ft.get(r) + ft.get(l - 1);
            }
            ft.upd(r, 1);
        }
    }
    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