Submission #516432

#	Time	Username	Problem	Language	Result	Execution time	Memory
516432		KoD	Index (COCI21_index)	C++17	0 / 110	1 ms	588 KiB

index

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

struct Fenwick {
    int size;
    vector<int> data;
    Fenwick(const int n) : size(n), data(n + 1) {}
    void add(int i, const int x) {
        i += 1;
        while (i <= size) {
            data[i] += x;
            i += i & -i;
        }
    }
    int pref(int i) const {
        int ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= i & -i;
        }
        return ret;
    }
    int fold(int l, int r) const {
        return pref(r) - pref(l);
    }
    void clear() {
        std::fill(data.begin(), data.end(), 0);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    vector<int> A(N);
    for (auto& x : A) {
        std::cin >> x;
    }
    vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](const int i, const int j) {
        return A[i] > A[j];
    });
    vector<int> L(Q), R(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> L[i] >> R[i];
        L[i] -= 1;
    }
    Fenwick fen(N);
    int idx = 0, back = 0;
    const auto prepare = [&](const int x) {
        if (idx > 0 and A[ord[idx - 1]] < x) {
            back += 1;
            assert(back <= 20);
            idx = 0;
            fen.clear();
        }
        while (idx < N and A[ord[idx]] >= x) {
            fen.add(ord[idx], 1);
            idx += 1;
        }
    };
    std::queue<tuple<int, int, vector<int>>> que;
    vector<int> all(Q);
    std::iota(all.begin(), all.end(), 0);
    que.emplace(0, N + 1, std::move(all));
    vector<int> ans(Q);
    while (!que.empty()) {
        const auto [l, r, vec] = std::move(que.front());
        que.pop();
        if (r - l == 1) {
            for (const int i : vec) {
                ans[i] = l;
            }
            continue;
        }
        const int m = (l + r) / 2;
        prepare(m);
        vector<int> low, high;
        for (const int i : vec) {
            (fen.fold(L[i], R[i]) >= m ? high : low).push_back(i);
        }
        if (!low.empty()) {
            que.emplace(l, m, std::move(low));
        }
        if (!high.empty()) {
            que.emplace(m, r, std::move(high));
        }
    }
    for (const int x : ans) {
        std::cout << x << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50