Submission #1244119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244119		ollelap	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	158 ms	149064 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();
    ll ans = 0;

    vector<queue<int>> pos(n);
    vector<int> cnt(n, 0);
    rep(i,0,n) {
        if (arr[i] > 0) {
            cnt[arr[i]]--;
            if (cnt[arr[i]] < 0) pos[arr[i]].push(i);
        }

        else {
            cnt[-arr[i]]++;

            if (cnt[-arr[i]] <= 0) {
                int j = pos[-arr[i]].front();
                pos[-arr[i]].pop();
                swap(arr[i], arr[j]);
                ans++;
            }
        }
    }


    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);


    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;
}

/*
int main() {
    int n;
    cin >> n;
    vector<int>arr(n);
    rep(i,0,n) cin >> arr[i];
    cout << count_swaps(arr) << endl;
}
*/

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