Submission #683841

#	Time	Username	Problem	Language	Result	Execution time	Memory
683841		PoonYaPat	Index (COCI21_index)	C++14	110 / 110	1845 ms	255420 KiB

index

#include <bits/stdc++.h>
using namespace std;

struct node {
    int val;
    node *L, *R;

    node(int val) : val(val),L(NULL),R(NULL) {}
    node(node *l, node *r) : val(0), L(l), R(r) {
        if (l) val+=l->val;
        if (r) val+=r->val;
    }
};

node* build(int l, int r) {
    if (l==r) return new node(0);
    else {
        int mid=(l+r)/2;
        return new node(build(l,mid),build(mid+1,r));
    }
}

node* update(node *v, int l, int r, int x, int val) {
    if (x>r || x<l) return v;
    if (l==r) return new node(v->val+val);
    int mid=(l+r)/2;
    return new node(update(v->L,l,mid,x,val),update(v->R,mid+1,r,x,val));
}

int query(node *v, int l, int r, int x, int y) {
    if (x>r || y<l) return 0;
    if (x<=l && r<=y) return v->val;
    int mid=(l+r)/2;
    return query(v->L,l,mid,x,y)+query(v->R,mid+1,r,x,y);
}

vector<node*> arr;
int n,q;
const int mx=200005;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    arr.push_back(build(1,mx));
    for (int i=1; i<=n; ++i) {
        int x; cin>>x;
        arr.push_back(update(update(arr.back(),1,mx,1,1),1,mx,x+1,-1));
    }

    while (q--) {
        int a,b; cin>>a>>b;
        int l=1,r=mx;
        while (l<r) {
            int mid=(l+r+1)/2;
            if (query(arr[b],1,mx,1,mid)-query(arr[a-1],1,mx,1,mid)>=mid) l=mid;
            else r=mid-1;
        }
        cout<<l<<"\n";
    }
}

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