Submission #164185

#	Time	Username	Problem	Language	Result	Execution time	Memory
164185		popovicirobert	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	108 ms	15000 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long

using namespace std;

struct Fenwick {
    vector <int> aib;
    int n;

    inline void init(int _n) {
        n = _n;
        aib.resize(n + 1);
    }

    inline void update(int pos, int val) {
        pos++;
        for(int i = pos; i <= n; i += lsb(i)) {
            aib[i] += val;
        }
    }

    inline int query(int pos) {
        pos++;
        int ans = 0;
        for(int i = pos; i > 0; i -= lsb(i)) {
            ans += aib[i];
        }
        return ans;
    }

    inline int sum(int l, int r) {
        return query(r) - query(l - 1);
    }
};

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

    vector < vector <int> > l(n + 1), r(n + 1);
    int i;

    for(i = 0; i < 2 * n; i++) {
        if(s[i] < 0) {
            l[-s[i]].push_back(i);
        }
        else {
            r[s[i]].push_back(i);
        }
    }

    for(i = 1; i <= n; i++) {
        sort(l[i].rbegin(), l[i].rend());
        sort(r[i].rbegin(), r[i].rend());
    }

    Fenwick fen; fen.init(2 * n);

    vector <bool> vis(2 * n);
    ll ans = 0;

    for(i = 0; i < 2 * n; i++) {
        if(vis[i]) continue;

        if(s[i] < 0) {
            int pos = r[-s[i]].back();
            vis[pos] = 1;

            ans += pos - i - fen.sum(i + 1, pos - 1) - 1;
            fen.update(pos, 1);
        }
        else {
            int pos = l[s[i]].back();
            vis[pos] = 1;

            ans += pos - i - fen.sum(i + 1, pos - 1);
            fen.update(pos, 1);
        }

        l[abs(s[i])].pop_back();
        r[abs(s[i])].pop_back();
    }

    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