Submission #204668

#	Time	Username	Problem	Language	Result	Execution time	Memory
204668		apostoldaniel854	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	425 ms	409720 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5;

queue <int> d[1 + 2 * N + 5];

typedef long long ll;
int n;
int aib[1 + N * 2];
int used[1 + N * 2];
int lsb (int x) {
    return x & -x;
}

void upd (int x, int y) {
    while (x <= n) {
        aib[x] += y;
        x += lsb (x);
    }
}

int qry (int x) {
    int ans = 0;
    while (x) {
        ans += aib[x];
        x -= lsb (x);
    }
    return ans;
}

ll count_swaps (vector <int> v) {
    n = v.size ();
    for (int i = 0; i < n; i++) {
        d[v[i] + N].push (i);
    }
    for (int i = 0; i < n; i++) {
        upd (i + 1, 1);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        d[v[i] + N].pop ();
        int j = d[N - v[i]].front();
        d[N - v[i]].pop();
        used[i] = 1;
        used[j] = 1;
        ans += qry (j + 1) - qry (i + 1) - 1;
        upd (i + 1, 1);
        upd (j + 1, -1);
        if (v[i] > v[j])
            ans++;
    }
    return ans;
}

/*int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    cin >> n;
    vector <int> v (n);
    for (auto &x : v)
        cin >> x;
    cout << count_swaps (v) << "\n";
    return 0;
}*/

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