Submission #1153960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153960		itslq	Index (COCI21_index)	C++20	60 / 110	2596 ms	50756 KiB

index

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

const int MAX = 2e5 + 10;
vector<int> P(MAX);

struct node {
    int l, r, m;
    vector<int> v;
    node *lc, *rc;

    node(int _l, int _r): l(_l), r(_r), m((_l + _r) >> 1) {
        if (l == r) {
            v.push_back(P[l]);
        } else {
            lc = new node(l, m);
            rc = new node(m + 1, r);

            v.resize(lc -> v.size() + rc -> v.size());
            auto lv = lc -> v.begin(), rv = rc -> v.begin(), it = v.begin();
            
            while (lv != lc -> v.end() && rv != rc -> v.end()) *(it++) = *((*lv < *rv ? lv : rv)++);
            while (lv != lc -> v.end()) *(it++) = *(lv++);
            while (rv != rc -> v.end()) *(it++) = *(rv++);
        }
    }

    int query(int _l, int _r, int _v) {
        if (l == _l && r == _r) return (int) (v.end() - lower_bound(v.begin(), v.end(), _v));
        if (_r <= m) return lc -> query(_l, _r, _v);
        if (_l > m) return rc -> query(_l, _r, _v);
        return lc -> query(_l, m, _v) + rc -> query(m + 1, _r, _v);
    }

} *root;

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

    int N, Q, L, R, l, r, m, ans;
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) cin >> P[i];

    root = new node(1, N);

    while (Q--) {
        cin >> L >> R;

        l = 1, r = R - L + 1;
        while (l <= r) {
            m = (7 * l + r) / 8;
            if (root -> 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: 0 / 50