제출 #661209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
661209		amsraman	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	142 ms	139340 KiB

shoes

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

template <typename T>
struct FenwickTree {
    int n;
    vector<T> bit;
    FenwickTree(int n): n(n), bit(n, 0) {};
    FenwickTree(vector<T> & init): n((int) init.size()), bit((int) init.size()) {
        copy(init.begin(), init.end(), bit.begin());
        for(int i = 1; i <= n; i++) {
            if(i + (i & -i) <= n) {
                bit[i + (i & -i) - 1] += bit[i - 1];
            }
        }
    }
    T qry(int k) {
        T ret = 0;
        for(k++; k > 0; k -= k & -k) {
            ret += bit[k - 1];
        }
        return ret;
    }
    T qry(int l, int r) {
        return qry(r) - qry(l - 1);
    }
    void upd(int k, T x) {
        for(k++; k <= n; k += k & -k) {
            bit[k - 1] += x;
        }
    }
};

ll count_swaps(vector<int> S) {
    int n = S.size();
    ll ans = 0;
    FenwickTree<int> ft(n);
    vector<queue<int>> lefts(n / 2), rights(n / 2);
    vector<bool> done(n, false);
    for(int i = 0; i < n; i++) {
        ft.upd(i, 1);
        if(S[i] < 0) {
            lefts[-S[i] - 1].push(i);
        } else {
            rights[S[i] - 1].push(i);
        }
    }
    for(int i = 0, j = 0; i < n / 2; i++) {
        while(done[j]) {
            ++j;
        }
        int left_thing, right_thing;
        if(S[j] < 0) {
            left_thing = j, right_thing = rights[-S[j] - 1].front();
        } else {
            left_thing = lefts[S[j] - 1].front(), right_thing = j;
        }
        lefts[abs(S[j]) - 1].pop(), rights[abs(S[j]) - 1].pop(), done[left_thing] = done[right_thing] = true;
        ft.upd(left_thing, -1); ans += ft.qry(left_thing);
        ft.upd(right_thing, -1); ans += ft.qry(right_thing);
    }
    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