제출 #1153903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153903		simuyu	Index (COCI21_index)	C++20	0 / 110	351 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 s, e, m, val;
    sum_node *l, *r;
    sum_node (int _s, int _e):
        s(_s), e(_e), m((_s+_e)/2), val(0) {
            if (s != e) {
                // not leaf
                l = new sum_node(s, m);
                r = new sum_node(m+1, e);
            }
        }

    void increment(ll idx, ll v) {
        if (s==e) {
            // leaf
            val += v;
            return;
        } else if (idx>m) {
            r->increment(idx, v);
        } else {
            l->increment(idx, v);
        }

        val = l->val + r->val;
    }

    ll sum(ll x, ll y) { // inclusive of both
        if ((x>y) || (x>e) || (y<s)) return 0; // invalid input
        if (s==e) return val;

        // if completely within range
        if ((x<s) && (y>e)) return val;

        return l->sum(x, y) + r->sum(x, y);
    }
};



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(0, 50005);
        }

    void update (ll idx, ll v) {
        if (s==e) {
            // leaf.
            counts->increment(v, 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); // 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, 50005);
        }

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


        // 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[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;
            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