Submission #1164250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164250		canhnam357	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	146 ms	138928 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
struct fenwick
{
    int n;
    vector<int> bit;
    fenwick() {}
    fenwick(int n)
    {
        this->n = n + 5;
        bit.resize(n + 5);
    }
    void add(int pos, int val)
    {
        while (pos < n)
        {
            bit[pos] += val;
            pos += pos & -pos;
        }
    }
    int get(int pos)
    {
        int ans = 0;
        while (pos)
        {
            ans += bit[pos];
            pos -= pos & -pos;
        }
        return ans;
    }
    int get(int l, int r)
    {
        return get(r) - get(l - 1);
    }
    int find(int k)
    {
        int sum = 0, pos = 0;
        for (int i = __lg(n); i >= 0; i--)
        {
            if (pos + (1 << i) < n && sum + bit[pos + (1 << i)] < k)
            {
                sum += bit[pos + (1 << i)];
                pos += (1 << i);
            }
        }
        return pos + 1;
    }
};
long long count_swaps(std::vector<int> s) {
    int n = s.size() / 2;
    fenwick tree(2 * n);
    vector<deque<int>> l(n + 1), r(n + 1);
    for (int i = 0; i < 2 * n; i++)
    {
        if (s[i] < 0) l[-s[i]].push_back(i + 1);
        else r[s[i]].push_back(i + 1);
    }
    vector<int> del(2 * n);
    long long ans = 0;
    for (int i = 1; i <= 2 * n; i++) tree.add(i, 1);
    for (int i = 0; i < 2 * n; i++)
    {
        if (del[i])
        {
            continue;
        }
        if (s[i] < 0)
        {
            l[-s[i]].pop_front();
            tree.add(i + 1, -1);
            ans += tree.get(r[-s[i]][0] - 1);
            tree.add(r[-s[i]][0], -1);
            del[r[-s[i]][0] - 1] = 1;
            r[-s[i]].pop_front();
        }
        else
        {
            r[s[i]].pop_front();
            tree.add(i + 1, -1);
            ans += tree.get(l[s[i]][0]);
            tree.add(l[s[i]][0], -1);
            del[l[s[i]][0] - 1] = 1;
            l[s[i]].pop_front();
        }
    }
    return ans;
}
// int main()
// {
//     cout << count_swaps({2, 1, -1, -2});
//     return 0;
// }

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