제출 #1167436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167436		sunflower	Index (COCI21_index)	C++17	60 / 110	2571 ms	48320 KiB

index

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int n, q;
#define MAX_N 200'200
int a[MAX_N + 2];

struct MST {
    vector <int> seg[4 * MAX_N + 2];

    vector <int> Merge(const vector <int> &a, const vector <int> &b) {
        vector <int> res;
        int i = 0, j = 0;
        while (i < SZ(a) && j < SZ(b)) {
            if (a[i] <= b[j]) {
                res.push_back(a[i++]);
            } else {
                res.push_back(b[j++]);
            }
        }

        while (i < SZ(a)) res.push_back(a[i++]);
        while (j < SZ(b)) res.push_back(b[j++]);

        return res;
    }

    void build(int id, int l, int r) {
        if (l == r) {
            seg[id].push_back(a[l]);
            return;
        }

        int g = (l + r) >> 1;
        build(id << 1, l, g);
        build(id << 1 | 1, g + 1, r);
        seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
    }

    int get(int id, int l, int r, int u, int v, const int &value) {
        if (l > v || u > r) return 0;
        if (u <= l && r <= v) {

            int lef = 0, rig = SZ(seg[id]) - 1, g, vt = -1;
            while (lef <= rig) {
                g = (lef + rig) >> 1;
                if (seg[id][g] >= value) vt = g, rig = g - 1;
                else lef = g + 1;
            }

            if (vt == -1) return 0;
            return SZ(seg[id]) - vt;
        }

        int g = (l + r) >> 1;
        return get(id << 1, l, g, u, v, value) + get(id << 1 | 1, g + 1, r, u, v, value);
    }
} st;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);

    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];

    st.build(1, 1, n);

    while (q--) {
        int L, R;
        cin >> L >> R;
        int l = 1, r = R - L + 1, g, vt = -1;
        while (l <= r) {
            g = (l + r) >> 1;
            if (st.get(1, 1, n, L, R, g) >= g) vt = g, l = g + 1;
            else r = g - 1;
        }

        if (vt == -1) vt = 0;

        cout << vt << "\n";
    }

    return 0;
}

/* Discipline - Calm */

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