Submission #405395

#	Time	Username	Problem	Language	Result	Execution time	Memory
405395		Sundavar	Index (COCI21_index)	C++14	110 / 110	995 ms	133476 KiB

index

#include <bits/stdc++.h>

using namespace std;

struct node{
    node* l = NULL,* r = NULL;
    int sum;
    node(node* l, node* r) : l(l), r(r){
        sum = (l ? l->sum : 0) + (r ? r->sum : 0);
    }
    node(int x) : sum(x){}
};
typedef node* pnode;
struct segTree{
    vector<pnode> root;
    int maxN;
    segTree(int n) : maxN(n){
        root.push_back(build(0, n));
    }
    pnode build(int l, int r){
        if(l == r-1) return new node(0);
        return new node(build(l, (l+r)/2), build((l+r)/2, r));
    }
    pnode update(pnode t, int poz, int c, int l, int r){
        if(l == r-1) return new node(t->sum + c);
        int m = (l+r)/2;
        if(poz < m) return new node(update(t->l, poz, c, l, m), t->r);
        return new node(t->l, update(t->r, poz, c, m, r));
    }
    void update(int poz, int c){
        root.push_back(update(root[root.size()-1], poz, c, 0, maxN));
    }
    int ask(pnode tl, pnode tr, int ex, int l, int r){
        if(l == r-1) return l;
        int m = (l+r)/2, sum = tr->r->sum - tl->r->sum;
        if(m <= sum+ex) return ask(tl->r, tr->r, ex, m, r);
        return ask(tl->l, tr->l, ex + sum, l, m);
    }
    int ask(int l, int r){
        return ask(root[l-1], root[r], 0, 0, maxN);
    }
};

int main(){
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vector<int> v(n);
    segTree tree = segTree(n);
    for(int i = 0; i < n; i++)
        cin>>v[i], tree.update(v[i], 1);
    while(m--){
        int l, r;
        cin>>l>>r;
        cout<<tree.ask(l, r)<<"\n";
    }
}

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