Submission #294397

#	Time	Username	Problem	Language	Result	Execution time	Memory
294397		albertolg101	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	199 ms	139820 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"

using namespace std;

long long count_swaps(vector<int> ar)
{
    int n = ar.size();
    ar.resize(n + 1);

    for(int i = n - 1; i >= 0; i--)
        ar[i + 1] = ar[i];

    vector<int> freq(n);
    vector<queue<int>> dis(n);


    function<bool(int, int)> diffSign = [](int a, int b)
    {
        return ((a < 0 and b > 0) or (a > 0 and b < 0));
    };

    long long ans = 0;
    vector<int> bit(n + 1, 0);

    function<void(int, int)> update = [&](int pos, int val)
    {
        for(;pos <= n; pos += (pos & -pos))
            bit[pos] += val;
    };

    function<int(int, int)> query = [&](int l, int r)
    {
        int Qans = 0;
        for(int pos = r; pos > 0; pos -= (pos & -pos))
            Qans += bit[pos];

        for(int pos = l; pos > 0; pos -= (pos & -pos))
            Qans -= bit[pos];

        return Qans;
    };

    for(int i = 1; i <= n; i++)
        update(i, 1);

    for(int i = 1; i <= n; i++)
    {
        if(diffSign(freq[abs(ar[i])], ar[i]))
        {
            int temp = ar[i] < 0;
            ar[i] = abs(ar[i]);

            (freq[ar[i]] < 0 ? freq[ar[i]]++ : freq[ar[i]]--);

            int last = dis[abs(ar[i])].front(); dis[abs(ar[i])].pop();

            ans += query(last, i - 1) + temp;
            update(i, -1);
            update(last, 1);
        }
        else
        {
            ( ar[i] < 0 ? freq[abs(ar[i])]-- : freq[abs(ar[i])]++);
            ar[i] = abs(ar[i]);
            dis[ar[i]].push(i);
        }
    }

    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