Submission #486228

#	Time	Username	Problem	Language	Result	Execution time	Memory
486228		diedie	Index (COCI21_index)	C++17	110 / 110	1152 ms	55820 KiB

index

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

const int maxN = 2e5 + 5;
const int maxT = 20 * maxN;

int n, nTest;
int p[maxN];

int idx;
struct Segment {
    int left, right, val;
} st[maxT];

int root[maxN];

void update(int pos, int& node, int l, int r, int h) {
    node = ++idx;
    st[node].left = st[pos].left;
    st[node].right = st[pos].right;
    st[node].val = st[pos].val + 1;

    if (l == r) return;

    int mid = (l + r) / 2;
    if (h <= mid)
        update(st[pos].left, st[node].left, l, mid, h);
    else
        update(st[pos].right, st[node].right, mid + 1, r, h);
}

int query(int node, int l, int r, int u, int v) {
    if (l > r || l > v || r < u) return 0;
    if (u <= l && r <= v) return st[node].val;

    int mid = (l + r) / 2;
    return query(st[node].left, l, mid, u, v) + query(st[node].right, mid + 1, r, u, v);
}

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

    cin >> n >> nTest;
    for (int i = 1; i <= n; i++)
        cin >> p[i];

    vector<vector<int>> a(maxN);
    for (int i = 1; i <= n; i++)
        a[p[i]].push_back(i);

    for (int i = maxN - 1; i >= 1; i--) {
        root[i] = root[i + 1];
        for (int j : a[i])
            update(root[i], root[i], 1, n, j);
    }

    while (nTest--) {
        int l, r; cin >> l >> r;

        int ans = 0;
        int low = 1, high = maxN - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (query(root[mid], 1, n, l, r) >= mid)
                ans = mid, low = mid + 1;
            else
                high = mid - 1;
        }
        cout << ans << '\n';
    }

    return 0;
}

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