Submission #1258935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258935		kawhiet	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	0 ms	328 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> t;

void upd(int k, int x) {
    k++;
    for (; k <= N; k += k & -k) {
        t[k] += x;
    }
}

int get(int k) {
    k++;
    int res = 0;
    for (; k >= 1; k -= k & -k) {
        res += t[k];
    }
    return res;
}

int get(int l, int r) {
    return get(r) - get(l - 1);
}

long long count_swaps(vector<int> a) {
    int n = a.size();
    N = n;
    t.resize(n + 1);
    vector<set<int>> pos(n + 1), neg(n + 1);
    for (int i = 0; i < n; i++) {
        if (a[i] > 0) {
            pos[a[i]].insert(i);
        }
        else {
            neg[-a[i]].insert(i);
        }
    }
    for (int i = 0; i < n; i++) {
        upd(i, 1);
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
        if (get(i, i) == 0) continue;
        int j = 0;
        if (a[i] > 0) {
            j = *neg[a[i]].upper_bound(i);
        }
        else {
            j = *pos[-a[i]].upper_bound(i);;
        }
        res += get(i + 1, j - 1) + (a[i] > 0);
        upd(i, -1);
        upd(j, -1);
    }
    return res;
}

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