Submission #1268586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268586		nathlol2	Index (COCI21_index)	C++20	20 / 110	2596 ms	30092 KiB

index

#include <bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;

struct segtree{
    struct node{
        int v;
        node *l, *r;
        node(int v) : v(v), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt[N], f;
    segtree(){
        f = new node(0);
        f->l = f->r = f;
    }
    void build(pnode &k, int l, int r){
        k = new node(0);
        int md = (l + r) / 2;
        if(l == r) return;
        build(k->l, l, md);
        build(k->r, md + 1, r);
    }
    void upd(pnode &k, pnode pv, int l, int r, int idx){
        k = new node(*pv);
        if(l == r) return k->v += 1, void();
        int md = (l + r) / 2;
        if(idx <= md) upd(k->l, pv->l, l, md, idx);
        else upd(k->r, pv->r, md + 1, r, idx);
        k->v = (k->l ? k->l->v : 0) + (k->r ? k->r->v : 0);
    }
    int qry(pnode k, int l, int r, int L, int R){
        if(r < L || l > R || !k) return 0;
        if(l == r) return k->v;
        int md = (l + r) / 2;
        return qry(k->l, l, md, L, R) + qry(k->r, md + 1, r, L, R); 
    }
}s;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;
    s.build(s.rt[0], 1, n);
    for(int i = 1;i<=n;i++){
        int x;
        cin >> x;
        s.upd(s.rt[i], s.rt[i - 1], 1, n, x);
    }
    while(q--){
        int l, r;
        cin >> l >> r;
        int L = 1, R = n, ans = -1;
        while(L <= R){
            int md = (L + R) / 2;
            if(s.qry(s.rt[r], 1, n, md, n) - s.qry(s.rt[l - 1], 1, n, md, n) >= md){
                ans = md;
                L = md + 1;
            }else{
                R = md - 1;
            }
        }
        cout << ans << '\n';
    }
}

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