Submission #144809

#	Time	Username	Problem	Language	Result	Execution time	Memory
144809		khrbuddy03	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	7 ms	6648 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

using lint = long long;

const int maxn = 1e5 + 9;

struct fenwick {
    vector<int> tree;
    fenwick(int _n) : tree(_n + 1, 0) {}
    lint get(int index) {
        lint sum = 0LL;
        while (0 < index) {
            sum += tree[index] * 1LL;
            index -= (index & -index);
        }
        return sum;
    }
    void add(int index, int value) {
        while (index < tree.size()) {
            tree[index] += value * 1LL;
            index += (index & -index);
        }
    }
};

lint count_swaps(vector<int> s) {
    int n = (int)s.size() / 2;
    vector<bool> check(n * 2, false);
    fenwick tree(n * 2);
    priority_queue<int> pq1[maxn], pq2[maxn];
    for (int i = 0; i < 2 * n; ++i) {
        if (s[i] > 0)
            pq1[s[i]].push(-i);
        else
            pq2[-s[i]].push(-i);
    }
    for (int i = 0; i < 2 * n; ++i) {
        if (check[i])
            continue;
        int pos;
        if (s[i] > 0) {
            pos = -pq2[s[i]].top();
            pq2[s[i]].pop();
            pq1[s[i]].pop();
            tree.add(i + 1, 1);
            tree.add(pos + 1, -1);
        } else {
            pos = -pq1[-s[i]].top();
            pq1[-s[i]].pop();
            pq2[-s[i]].pop();
            tree.add(i + 2, 1);
            tree.add(pos + 1, -1);
        }
        check[pos] = true;
    }
    lint ret = 0;
    for (int i = 1; i <= 2 * n; ++i)
        ret += tree.get(i) * 1LL;
    return ret;
}

Compilation message (stderr)

shoes.cpp: In member function 'void fenwick::add(int, int)':
shoes.cpp:21:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (index < tree.size()) {
                ~~~~~~^~~~~~~~~~~~~

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