Submission #1268589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268589		nathlol2	Index (COCI21_index)	C++20	110 / 110	310 ms	132760 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];
    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, pnode q, int l, int r, int n, int pv){
        if(l == r) return l;
        int md = (l + r) / 2;
        int lc = k->l->v - q->l->v;
        if(lc + pv >= n - md + 1) return qry(k->l, q->l, l, md, n, pv);
        else return qry(k->r, q->r, md + 1, r, n, pv + lc);
    }
}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, n - x + 1);
    }
    while(q--){
        int l, r;
        cin >> l >> r;
        cout << n - s.qry(s.rt[r], s.rt[l - 1], 1, n, n, 0) + 1 << '\n';
    }
}

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