Submission #1026020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026020		vanea	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	165 ms	14932 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 2e6+10;

bool vis[mxN];
int st[mxN];
int n;

void upd(int idx, int x) {
    st[idx += n] = x;
    for(idx >>= 1; idx >= 1; idx >>= 1) st[idx] = st[idx*2] + st[idx*2+1];
}

int query(int l, int r) {
    ++r;
    int ans = 0;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if(l & 1) ans += st[l++];
        if(r & 1) ans += st[--r];
    }
    return ans;
}

ll count_swaps(vector<int> v) {
    n = v.size();
    ll ans = 0;
    multiset<array<int, 2>> m;
    for(int i = 0; i < n; i++) {
        m.insert({v[i], i});
    }
    for(int i = 0; i < n; i++) {
        if(vis[i]) continue;
        auto it = m.lower_bound({-v[i], -1});
        int idx = (*it)[1];
        int mn = query(i+1, idx-1);
        vis[i] = vis[idx] = true;
        m.erase(it);
        m.erase({v[i], i});
        if(v[i] > 0) {
            ans += (idx-i)-mn;
        }
        else {
            ans += (idx-i-1)-mn;
        }
        upd(i, 1);
        upd(idx, 1);
    }
    return ans;
}

/*
int main()
{
    ll ans = count_swaps({2, 1, -1, -2});
    cout << 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