제출 #822854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
822854		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	105 ms	70440 KiB

shoes

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

using namespace std;

typedef long long ll;

int tree[200200];

void update(int i, int val) {
    for(; i < 200200; i += -i&i) {
        tree[i] += val;
    }
}

int get(int x) {
    int ans = 0;
    for(; x; ans += tree[x], x ^= -x&x);
    return ans;
}

queue < int > q[100100];

ll count_swaps(vector< int > s) {
    int n = s.size();
    ll ans = 0;
    for(int i = 0, j; i < n; ++ i) {
        j = abs(s[i]);
        if(q[j].empty() || s[q[j].front()] == s[i]) {
            q[j].push(i);
        } else {
            ans += i - (q[j].front() + get(q[j].front() + 1)) - (s[i] > 0);
            update(q[j].front() + 1, 1);
            update(i + 1, -1);
            q[j].pop();
        }
    }
    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