Submission #715822

#	Time	Username	Problem	Language	Result	Execution time	Memory
715822		TheSahib	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	389 ms	31308 KiB

shoes

#include <bits/stdc++.h>

#define ll long long
#define i128 __int128_t
#define pii pair<int, int>
#define oo 1e9

using namespace std;

int n;
vector<int> tree;

void update(int pos, int val){
    while(pos <= n){
        tree[pos] += val;
        pos += (pos & (-pos));
    }
}

int ask(int l, int r){
    if(l > r) return 0;
    if(l != 1) return ask(1, r) - ask(1, l - 1);
    int ans = 0;
    while(r > 0){
        ans += tree[r];
        r -= (r & (-r));
    }
    return ans;
}

ll count_swaps(vector<int> S){
    n = S.size();
    tree.resize(n + 5);
    fill(tree.begin(), tree.end(), 0);

    map<int, set<int>> mp;
    for (int i = 0; i < n; i++)
    {
        update(i + 1, 1);
        mp[S[i]].insert(i + 1);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if(ask(i, i) == 0){
            continue;
        }
        set<int> &s = mp[-S[i - 1]];
        auto itr = s.upper_bound(i);
        
        if(S[i - 1] >= 0){
            ans += ask(i, (*itr) - 1);
        }
        else{
            ans += ask(i + 1, (*itr) - 1);  
        }
        update(i, 1);
        update(*itr, -1);
        
        s.erase(itr);
        mp[S[i]].erase(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