Submission #1040660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040660		LaMatematica14	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	143 ms	140780 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<18;
vector<int> p(maxn<<1);

long long q(int a, int l, int r, int fr) {
    if (r <= fr) return p[a];
    int m = (l+r)/2;
    return q(a<<1, l, m, fr)+((m<fr)?q(a<<1|1, m, r, fr):0);
}

void upd(int a) {
    a += maxn;
    for (; a > 0; a>>=1) p[a]--;
}

long long count_swaps(vector<int> S) {
    int n = S.size();
    vector<queue<int>> r(n);
    for (int i = 0; i < n; i++) {
        r[abs(S[i]*2)+min(0, abs(S[i])/S[i])-1].push(i);
    }
    for (int i = 0; i < n; i++) p[i+maxn] = 1;
    for (int i = maxn-1; i > 0; i--) p[i] = p[i<<1] + p[i<<1|1];
    long long tot = 0;
    for (int i = 0; i < n; i++) {
        if (p[i+maxn] < 1) continue;
        upd(i);
        if (S[i] > 0) tot++;
        r[abs(S[i]*2)+min(0, abs(S[i])/S[i])-1].pop();
        int pos = r[abs(-S[i]*2)+min(0, abs(-S[i])/-S[i])-1].front();
        r[abs(-S[i]*2)+min(0, abs(-S[i])/-S[i])-1].pop();
        tot += q(1, 0, maxn, pos);
        upd(pos);
    }
    return tot;
}

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