제출 #760173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
760173		thinknoexit	Arranging Shoes (IOI19_shoes)	C++17	15 / 100	117 ms	72536 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int fw[200200];
void update(int v, int w) {
    for (int i = v;i <= 200000;i += i & -i) fw[i] += w;
}
int query(int v) {
    int ans = 0;
    for (int i = v;i > 0;i -= i & -i) ans += fw[i];
    return ans;
}
ll count_swaps(vector<int> v) {
    ll ans = 0;
    int n = (int)v.size();
    queue<int> pos[100100];
    queue<pair<int, int>> q;
    for (int i = 0;i < n;i++) {
        if (v[i] < 0) {
            q.push({ -v[i],i });
        }
        else {
            pos[v[i]].push(i);
        }
    }
    int cnt = 0;
    while (!q.empty()) {
        auto x = q.front();
        q.pop();
        int val = x.first, i = x.second;
        ans += query(i) + i - cnt;
        update(1, 1), update(i + 1, -1);
        ans += query(pos[val].front()) + pos[val].front() - (cnt + 1);
        update(1, 1), update(pos[val].front() + 1, -1);
        pos[val].pop();
        cnt += 2;
    }
    return ans;
}

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