Submission #1188756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188756		GoBananas69	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	0 ms	328 KiB

shoes

#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;

struct _ {
    int n = 0;
    vector<int> nums, st;
    void build(int i, int L, int R) {
        if (L == R) {
            st[i] = 1;
            return;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        build(x, L, m);
        build(y, m + 1, R);
        st[i] = st[x] + st[y];
    }
    int query(int i, int L, int R, int l, int r) {
        if (l > r) return 0;
        if (L == l && r == R) {
            return st[i];
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (r <= m) {
            return query(x, L, m, l, r);
        } else if (l > m) {
            return query(y, m + 1, R, l, r);
        } else {
            int q1 = query(x, L, m, l, m);
            int q2 = query(y, m + 1, R, m + 1, r);
            return q1 + q2;
        }
    }
    void update(int i, int L, int R, int p) {
        if (L == R) {
            st[i] = 0;
            return;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (p <= m) {
            update(x, L, m, p);
        } else {
            update(y, m + 1, R, p);
        }
        st[i] = st[x] + st[y];
    }
    void update(int p) {
        update(0, 0, n - 1, p);
    }
    int query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }
    void build(vector<int> &s) {
        n = s.size() + 1;
        nums = s;
        st.resize(4 * n);
        build(0, 0, n - 1);
    }
} tree;

int find(int x) {
    if (x < 0)
        return abs(x) * 2 - 1;
    else
        return abs(x) * 2;
}

ll count_swaps(vector<int> s) {
    int n = s.size() / 2;
    int m = s.size();
    int sz = 0;
    for (int i = 0; i < m; ++i) {
        int x = find(s[i]);
        sz = max(sz, x);
    }
    vector<queue<int>> pos(sz + 1);
    for (int i = 0; i < m; ++i) {
        int x = find(s[i]);
        pos[x].push(i);
    }
    tree.build(s);
    int res = 0;
    for (int l = 0; l < m; ++l) {
        int x = find(-s[l]);
        int r = pos[x].front();
        pos[x].pop();
        if (s[l] > s[r]) {
            res += tree.query(l, r - 1);
            tree.update(l);
        } else {
            res += tree.query(l + 1, r - 1);
            tree.update(l + 1);
        }
        tree.update(r - 1);
    }
    return res;
}

// int main() {
//     cin.tie(0)->sync_with_stdio(0);
//     vector<vector<int>> tc{
//         {2, -1, 3, -4, -2, 4, -3, 1}};
//     for (auto &v : tc) {
//         cout << count_swaps(v) << '\n';
//     }
// }

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