Submission #434823

#	Time	Username	Problem	Language	Result	Execution time	Memory
434823		magmag	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	31 ms	4176 KiB

shoes

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

const int mxN = 2e5+3;
ll idx[mxN];

struct FenwickTree {
    ll tr[mxN];

    ll LSB(ll x) {
        return (x) & (-x);
    }

    void add(ll i) {
        for (; i < mxN; i += LSB(i))++tr[i];
    }

    ll rsq(ll i) {
        ll s = 0;
        for (; i > 0; i -= LSB(i))s += tr[i];
        return s;
    }

    ll rsq(ll i, ll j) {
        return rsq(j) - (i > 1 ? rsq(i-1) : 0);
    }
};

long long count_swaps(std::vector<int> s) {
    int n = s.size();

    for (int i = 1; i <= n; ++i) {
        idx[abs(s[i-1])] = i;
    }

    FenwickTree ft;

    ll ans = 0;

    for (int i = 1; i <= n; ++i) {
        int curr = s[i-1];
        if (idx[abs(curr)] == i)continue;
        int nidx = idx[abs(curr)];

        ll dist = nidx - i - 1 - ft.rsq(i, nidx);

        if (s[i-1] > 0)++dist;
        ans += dist;
        ft.add(nidx);
    }
    return ans;
}

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