Submission #1153939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153939		jmuzhen	Index (COCI21_index)	C++20	110 / 110	2419 ms	51236 KiB

index

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

struct node
{
    int s, e, m;
    vector<int> v;
    node *l = nullptr, *r = nullptr;

    node(int s, int e) {
        this->s = s; this->e = e; this->m = (s+e)/2;
        if (s == e) return;
        l = new node(s, m);
        r = new node(m+1, e);
    }

    void build(vector<int>& A) {
        if (s == e) {
            v = {A[s]};
            return;
        }
        // build children
        l->build(A);
        r->build(A);

        v.resize(l->v.size()+r->v.size());
        // merge l, r
        ranges::merge(l->v, r->v, v.begin());
    }

    int query(int x, int y, int val) {
        // number of elements >= val in x..y

        // if not covered
        if (e < x || y < s) return 0;

        // if completely covered
        if (x <= s && e <= y) {
            auto it = lower_bound(v.begin(), v.end(), val);
            auto num = v.size() - (it - v.begin());
            return num;
        }

        // partially covered
        return (l->query(x,y,val) + r->query(x,y,val));
    }
};

int n, q;

int query(node *seg, int l, int r) {
    int low = 0, high = n+5;
    int ans = 0;
    while (low < high) {
        int mid = (low+high)/2; // number of citations
        int res = seg->query(l,r,mid);
        if (res >= mid) {
            // too many can fit the description, try increasing mid
            ans = mid;
            low = mid+1;
        }
        else {
            high = mid;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q;
    vector<int> A(n); for (int i = 0; i < n; i++) cin >> A[i];
    node *seg = new node(0, n-1);
    seg->build(A);

    while (q--) {
        int l,r; cin >> l >> r; l--,r--;
        cout << query(seg, l, r) << "\n";
    }
}

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