Submission #760201

#	Time	Username	Problem	Language	Result	Execution time	Memory
760201		thinknoexit	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	69 ms	135028 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll fw[200200];
queue<int> pos[100100], pos2[100100];
bool ch[200200];
void update(int v, int w) {
    for (int i = v + 1;i <= 200000;i += i & -i) fw[i] += w;
}
ll query(int v) {
    ll ans = 0;
    for (int i = v + 1;i > 0;i -= i & -i) ans += fw[i];
    return ans;
}
ll count_swaps(vector<int> v) {
    ll ans = 0;
    int n = (int)v.size();
    for (int i = 0;i < n;i++) {
        if (v[i] < 0) {
            pos2[-v[i]].push(i);
        }
        else {
            pos[v[i]].push(i);
        }
    }
    for (int i = 0;i < n;i++) {
        if (ch[i]) continue;
        if (v[i] < 0) {
            v[i] = -v[i];
            int nowpos = i + query(i);
            ans += pos[v[i]].front() - nowpos - 1;
            update(1, 1), update(pos[v[i]].front() + 1, -1);
        }
        else {
            int nowpos = i + query(i);
            ans += pos2[v[i]].front() - nowpos;
            update(1, 1), update(pos2[v[i]].front() + 1, -1);
        }
        pos[v[i]].pop();
        pos2[v[i]].pop();
    }
    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