제출 #1286396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286396		harryleee	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	289 ms	179976 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

long long count_swaps(vector<int> a){
    int n = (int)a.size() / 2;

    vector<queue<int>> q(2 * n + 1);
    vector<int> last_ind(a.size());

    for (int i = 0; i < (int)a.size(); ++i){
        if (q[-a[i] + n].empty()){
            q[a[i] + n].push(i);
            last_ind[i] = i;
        }
        else{
            int pre = q[-a[i] + n].front();
            q[-a[i] + n].pop();
            last_ind[i] = pre;
        }
    }

    struct SEGMENT_TREE{
        vector<vector<int>> st;
        SEGMENT_TREE(int m, const vector<int>& vec){
            st.resize(4 * m);
            build(1, 0, m - 1, vec);
        }
        void build(int ind, int l, int r, const vector<int>& vec){
            if (l == r){
                st[ind].push_back(vec[l]);
                return;
            }
            int mid = (l + r) >> 1;
            build(ind << 1, l, mid, vec);
            build(ind << 1 | 1, mid + 1, r, vec);

            const vector<int>& L = st[ind << 1];
            const vector<int>& R = st[ind << 1 | 1];
            vector<int> tmp;
            tmp.reserve(L.size() + R.size());
            size_t i = 0, j = 0;
            while (i < L.size() && j < R.size()){
                if (L[i] <= R[j]) tmp.push_back(L[i++]);
                else tmp.push_back(R[j++]);
            }
            while (i < L.size()) tmp.push_back(L[i++]);
            while (j < R.size()) tmp.push_back(R[j++]);
            st[ind].swap(tmp);
        }
        long long get(int ind, int l, int r, int lb, int rb, int val){
            if (lb > rb) return 0;
            if (lb <= l && r <= rb){
                int it = upper_bound(st[ind].begin(), st[ind].end(), val) - st[ind].begin();
                return (long long)st[ind].size() - it;
            }
            int mid = (l + r) >> 1;
            long long ans = 0;
            if (lb <= mid) ans += get(ind << 1, l, mid, lb, rb, val);
            if (rb > mid)  ans += get(ind << 1 | 1, mid + 1, r, lb, rb, val);
            return ans;
        }
    };

    SEGMENT_TREE seg((int)a.size(), last_ind);

    long long res = 0;
    for (int i = 0; i < (int)a.size(); ++i) if (last_ind[i] != i){
        res += seg.get(1, 0, (int)a.size() - 1, last_ind[i] + 1, i - 1, last_ind[i]);
        if (a[last_ind[i]] > 0) res++;
    }

    return res;
}

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