Submission #1244107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244107		ollelap	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	54 ms	13640 KiB

shoes

#include "shoes.h"

using namespace std;
#include <bits/stdc++.h>

#define rep(i,a,b) for(int i = a; i < b; i++)
typedef long long ll;


// SUM TREE
struct SegmTree {
vector<ll> T; int n;
SegmTree(int n) : T(2 * n, (ll)0), n(n) {}

    void Update(int pos, ll val) {
        for (T[pos += n] = val; pos > 1; pos /= 2)
        T[pos / 2] = T[pos] + T[pos ^ 1];
    }

    ll Query(int b, int e) {
        ll res = 0;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) res = res + T[b++];
            if (e % 2) res = res + T[--e];
        }
        return res;
    }
};


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

    vector<vector<int>> p2index(n);
    vector<int> pointer(n, 0);
    rep(i,0,n) if (arr[i] > 0) p2index[arr[i]].push_back(i);


    SegmTree tr(n);

    ll ans = 0;

    rep(i,0,n) {
        if (arr[i] > 0) continue;

        ll here = i - tr.Query(0, i);
        tr.Update(i, 1);
        int nei = p2index[-arr[i]][pointer[-arr[i]]];
        here += nei - tr.Query(0, nei);
        tr.Update(nei, 1);
        pointer[-arr[i]]++;

        ans += here;
    }

    return ans;
}

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