Submission #1311425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311425		nikoloz-ch	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	439 ms	25468 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

long long count_swaps(vector<int> S) {
    int n = S.size();long long ans = 0;
    vector<int> bit(n + 1, 0);
    auto up = [&](int i, int v){
        for (; i <= n; i += i & -i) bit[i] += v;
    };
    auto qr = [&](int i){
        int s = 0;
        for(;i > 0; i -= i & -i) s += bit[i];
        return s;
    };
    map<int, vector<int>> mp;
    for(int i = n - 1; i >= 0; i--) mp[S[i]].push_back(i);
    vector<int> v(n, 0);
    for(int i = 0; i < n; i++) {
        if(v[i]) continue; int x = S[i], j = mp[-x].back();
        mp[x].pop_back(); mp[-x].pop_back();
        v[j] = 1; ans += (j - i - (x < 0 ? 1 : 0) + qr(j + 1) - qr(i + 1));
        up(i + 1, 1); up(j + 1, -1);
    }
    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