Submission #921415

#	Time	Username	Problem	Language	Result	Execution time	Memory
921415		AverageAmogusEnjoyer	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	335 ms	27296 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
constexpr int nax = 200200;
int st[4*nax];
int n;
void upd(int p,int u=1,int tl=1,int tr=n) {
    if (tl == tr) {
        st[u] = 1;
        return;
    }
    int mid=(tl+tr)/2;
    if (p<=mid) {
        upd(p,2*u,tl,mid);
    } else {
        upd(p,2*u+1,mid+1,tr);
    }
    st[u] = st[2*u]+st[2*u+1];
}
int qry(int l,int r,int u=1,int tl=1,int tr=n) {
    if (l > r) { return 0; }
    if (l == tl && r == tr) {
        return st[u];
    }
    int mid = (tl+tr)/2;
    return qry(l,min(mid,r),2*u,tl,mid)+qry(max(mid+1,l),r,2*u+1,mid+1,tr);
}
ll count_swaps(vector<int> a) {
    ll ans = 0;
    n = (int)a.size();
    map<int,vector<int>> p;
    for (int i=n-1;i>=0;i--) {
        p[a[i]].push_back(i);
    }
    vector<bool> done(n);
    for (int i=0;i<n;i++) {
        if (done[i]) { continue; }
        done[i] = true;
        assert(!p[-a[i]].empty());
        int nxt = p[-a[i]].back();
        done[nxt] = true;
        p[-a[i]].pop_back();
        assert(!p[a[i]].empty() && p[a[i]].back() == i);
        p[a[i]].pop_back();
        int add = max(0,nxt-(i+1)-qry(i+1,nxt)); 
        // cout << add << " ";
        ans += add; 
        if (a[i] > 0) {
            ans++;
            // cout << "added 1 ";
        }
        // cout << ans << endl;
        upd(nxt);
    }
    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