Submission #730625

#	Time	Username	Problem	Language	Result	Execution time	Memory
730625		danikoynov	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	337 ms	31908 KiB

shoes

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

using namespace std;
typedef long long ll;

map < int, set < int > > mp;
const int maxn = 2e5 + 10;
int fen[maxn];

void add(int v, int val)
{
    v ++;
    for (int i = v; i < maxn; i += (i & -i))
        fen[i] += val;
}

int sum(int v)
{
    v ++;
    int s = 0;
    for (int i = v; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

ll query(int left, int right)
{
    return sum(right) - sum(left - 1);
}
int used[maxn];
long long count_swaps(vector<int> s)
{
    int n = s.size() / 2;
    for (int i = 0; i < 2 * n; i ++)
        mp[s[i]].insert(i);


    ll ans = 0;
    for (int i = 0; i < 2 * n; i ++ )
    {

        if (used[i])
            continue;
        used[i] = 1;
        add(i, 1);
        mp[s[i]].erase(i);
        int pt = *mp[-s[i]].begin();
        mp[-s[i]].erase(pt);
        ///cout << i << " " << pt << endl;
        ans = (ans + (ll)(pt - i - 1));
        //cout << i << " " << pt << endl;
        ans = ans - query(i + 1, pt);
        used[pt] = 1;
        add(pt, 1);
        if (s[i] > 0)
            ans ++;

    }
    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