Submission #212339

#	Time	Username	Problem	Language	Result	Execution time	Memory
212339		jk89	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	99 ms	135032 KiB

shoes

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define f first
#define s second

const int MAXN = 1e5 + 3;
const int MAXM = 512 * 1024 + 3;

int tree[MAXM];
deque<int> q[MAXN];
deque<int> q2[MAXN];
long long ret;

long long suma(int v) {
    ret = 0;
    while (v) {
        ret += tree[v];
        v /= 2;
    }
    return ret;
}

void dodaj(int v, int x, int y, int a, int b) {
    if (y < a || x > b)
        return;
    if (x >= a && y <= b) {
        tree[v]++;
        return;
    }
    dodaj(v * 2, x, (x + y) / 2, a, b);
    dodaj(v * 2 + 1, (x + y) / 2 + 1, y, a, b);
}

long long count_swaps(vector<int> v) {
    long long ans = 0, temp;
    int n = v.size();
    int x, y, pot = 1;
    while (pot < n)
        pot *= 2;
    for (int i = 1; i <= n; i++) {
        x = v[i - 1];
        if (x < 0) {
            x = -x;
            if (q[x].empty()) {
                q2[x].push_back(i);
                continue;
            }
            y = q[x].front();
            q[x].pop_front();
            temp = x - y + 1 - suma(y + pot - 1);
            dodaj(1, 1, pot, y, x);
            ans += temp + 1;
        }
        else {
            if (q2[x].empty()) {
                q[x].push_back(i);
                continue;
            }
            y = q2[x].front();
            q2[x].pop_front();
            temp = x - y + 1 - suma(y + pot - 1);
            dodaj(1, 1, pot, y, x);
            ans += temp;
        }
    }
    return ans;
}

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