Submission #373614

#	Time	Username	Problem	Language	Result	Execution time	Memory
373614		SnowFlake7	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	277 ms	207724 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

queue <int> q[300005];
int v[300005],aib[300005],n;
long long s;

void update(int poz, int val) {
    for (int i = poz;i <= n;i += i&(-i))
        aib[i] += val;
}
long long query(int poz) {
    s = 0;
    for (int i = poz;i > 0;i -= i&(-i))
        s += aib[i];
    return s;
}
int f(int x) {
    if (x > 0)
        return x + n;
    else
        return -x;
}
long long count_swaps(vector<int> s) {
    long long ans = 0,a;
    n = s.size();
    for (int i = 0;i < n;i++) {
        v[i + 1] = s[i];
        q[f(v[i + 1])].push(i + 1);
        update(i + 1, 1);
    }
    for (int i = 1;i <= n;i++) {
        if (q[f(v[i])].front() != i)
            continue;
        q[f(v[i])].pop();
        if (v[i] < 0)
            update(i, -1);
        a = q[f(-v[i])].front();
        q[f(-v[i])].pop();
        update(a, -1);
        ans += query(a);
        if (v[i] > 0)
            update(i, -1);
    }
    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