Submission #1154012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154012		itslq	Index (COCI21_index)	C++20	110 / 110	2456 ms	35072 KiB

index

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

int N;
const int MAX = 2e5 + 10;
vector<int> tree[2 * MAX];


int query(int l, int r, int v) {  
    int S = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1) {
            S += tree[l].end() - lower_bound(tree[l].begin(), tree[l].end(), v);
            l++;
        }
        if (r & 1) {
            r--;
            S += tree[r].end() - lower_bound(tree[r].begin(), tree[r].end(), v);
        }
    } 
    return S; 
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int Q, L, R, l, r, m, ans, P;
    cin >> N >> Q;

    for (int i = 0; i < N; i++) {
        cin >> P;
        tree[N + i].push_back(P);
    }
    for (int i = N - 1; i > 0; i--) {
        vector<int>& lv = tree[(i << 1)];
        vector<int>& rv = tree[(i << 1) | 1];

        tree[i].resize(lv.size() + rv.size());
        auto lp = lv.begin(), rp = rv.begin(), it = tree[i].begin();
        
        while (lp != lv.end() && rp != rv.end()) *(it++) = *((*lp < *rp ? lp : rp)++);
        while (lp != lv.end()) *(it++) = *(lp++);
        while (rp != rv.end()) *(it++) = *(rp++);
    }

    while (Q--) {
        cin >> L >> R;
        l = 1, r = R - L + 1, L--;
        while (l <= r) {
            m = (l + r) >> 1;
            if (query(L, R, m) >= m) {
                ans = m;
                l = ++m;
            } else {
                r = --m;
            }
        }

        cout << ans << '\n';
    }
}

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