Submission #1153929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153929		simuyu	Index (COCI21_index)	C++20	0 / 110	256 ms	589824 KiB

index

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long

ll N, Q;
ll p[200005];




struct sum_node {
    // point update range query sum segment tree
    ll N;
    ll vals[500005*4 + 3];
    sum_node (ll _N) {
        N = _N;
        for (ll i=0; i<_N; i++) {
            vals[i] = 0;
        }
    }

    void increment(ll idx, ll v, ll s, ll e, ll node) {
        if (s==e) {
            // leaf
            //cout << "INCREMENTED AT NODE " << node << endl;
            vals[node] += v;
            return;
        } else if (idx > (s+e)/2 ) {
            increment(idx, v, (s+e)/2 + 1, e, node*2 +1);
        } else {
            increment(idx, v, s, (s+e)/2, node*2);
        }

        vals[node] = vals[node*2] + vals[node*2 + 1];
    }

    ll sum(ll x, ll y, ll s, ll e, ll node) { // inclusive of both
        if ((x>y) || (x>e) || (y<s)) return 0; // invalid input
        if (s==e) {
            //cout << "PROVIDING VALUE " << x << ' ' << y << " AT NODE " << node << endl;
            return vals[node];
        }

        // if completely within range
        if ((x<=s) && (e<=y)) return vals[node];

        return sum(x, y, s, (s+e)/2, node*2) + sum(x, y, (s+e)/2 + 1, e, node*2 + 1);
    }
};



struct node {
    ll s, e, m;
    //int counts[200005];
    sum_node *counts;
    node *l, *r;
    node (int _s, int _e) :
        s(_s), e(_e), m((_s+_e)/2) {
            if (s != e) { //not leaf node
                l = new node(s, m);
                r = new node(m+1, e);
            }

            //for (int i=0; i<200005; i++) counts[i]=0;
            counts = new sum_node(50005); // 1-indexed
        }

    void update (ll idx, ll v) {
        if (s==e) {
            // leaf.
            counts->increment(v, 1, 1, 50005, 1);
            return;
        } else if (idx>m) {
            r->update(idx, v);
        } else {
            l->update(idx, v);
        }

        // this is a counts segment tree...
        counts->increment(v, 1, 1, 50005, 1); // haha it's actually just this
    }

    ll get_h_cnt(ll h, ll x, ll y) { // inclusive of both endpoints
        // sum of all the counts[h].
        if ((x>y) || (x>e) || (y<s)) return 0; // invalid

        if (x==y) { // leaf
            return counts->sum(h, 50004, 1, 50005, 1);
        }

        // if completely within range
        if ((s>=x) && (e<=y)) {
            return counts->sum(h, 50004, 1, 50005, 1);
        }


        // else, consider children
        return r->get_h_cnt(h, x, y) + l->get_h_cnt(h, x, y); // if out of range it'll return 0 so this is fine
    }

    bool try_h(ll h, ll x, ll y) {
        return get_h_cnt(h, x, y) >= h;

    }

} *root;

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


    cin >> N >> Q;

    root = new node(1, N);

    for (ll i=0; i<N; i++) {
        cin >> p[i];
        root->update(i+1, p[i]);
    }

    /*cout << "COUNTS: ";
    for (ll i=0; i<N; i++) {
        cout << root->counts->sum(i, i, 1, 50005, 1) << ' ';
    }
    cout << endl;

    cout << "VALS: ";
    for (ll i=0; i<N*4+3; i++) {
        cout << root->counts->vals[i] << ' ';
    }
    cout << endl;*/

    ll l, r;
    ll low, high, mid;
    for (ll q=0; q<Q; q++) {
        cin >> l >> r;
        low = 0;
        high = r-l+1;
        while (high-low > 1) {
            mid = (high+low)/2;
            //cout << "TRY H=" << mid << "; COUNT=" << root->get_h_cnt(mid, l, r) << endl;
            //cout << "TRY H=" << mid << "; COUNT=" << root->get_h_cnt(mid, l, r) << endl;
            if (root->try_h(mid, l, r)) {
                // means that mid is okay
                low = mid; // so low is guaranteed okay, as try_h(mid) or 0 (0 is always attainable)
            } else {
                high = mid;
            }
        }

        if (root->try_h(high, l, r)) {
            // if high works too, then just swap w low. in the end, low wld the the one we use
            swap(low, high);
        }

        // low is the answer
        cout << low << '\n';

    }

    return 0;
}

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