Submission #689928

#	Time	Username	Problem	Language	Result	Execution time	Memory
689928		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	304 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 + 1);
    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(S[i - 1] > 0){
            set<int> &s = mp[-S[i - 1]];
            auto itr1 = s.upper_bound(i);
            auto itr2 = itr1;

            int dif1 = oo, dif2 = oo;
            if(itr1 != s.end()){
                dif1 = ask(i, (*itr1) - 1);
            }
            if(itr1 != s.begin()){
                itr2 = prev(itr2);
                dif2 = ask((*itr2) + 1, i - 1);
            }
            if(dif1 <= dif2){
                update(i, 1);
                update(*itr1, - 1);
                ans += dif1;
                s.erase(itr1);
            }
            else{
                update(i, 1);
                update(*itr2, -1);
                ans += dif2;
                s.erase(itr2);
            }
        }
    }
    return ans;
}

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