Submission #1205543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205543		KindaGoodGames	Index (COCI21_index)	C++20	110 / 110	531 ms	167148 KiB

index

/*
    Start: 21:22
    First Submission: 21:41
    AC: 21:42 (First Try!!!!)

    Only ~20 Minutes for implementation! (W)

    Solution Idea: 
    
    We see that for any interval, if h is a *possible* index, then so must h-1 be too, since the required amount of elements to be atleast some value
    got less. Furthermore, the amount of "eligble" items increased, since before they needed to be atleast h and now only h-1. 

    Thus we can derive that wether a h-value is valid is monoton. Thus we can conclude to use binary search. 

    We now want to be able to get the amount of numbers greater or equal h and then at each step binary search wether the using the current h,
    we have atleast h items that are >= h. 

    We also see that we need to consider the amount of occurences for each number in an interval [l;r], 
    which reminds us of using persistent segment trees, similiarly to the kth-smallest number problem.

    Thus we can build n segment trees of length MAXA, which each contain the amount of occurence for each element. 
    The segment tree containing the frequency of the elements is now seg[r]-seg[l]. 

    Now to binary search, let the current range be [l;r] and m := (l+r)/2.  
    If we can take h = m, then the result must be atleast m, thus we could move to [m;r]. 
    However, if we can't take h =m, then the result has to be atmost m-1, thus we move to [l,m-1]. 

    Now to check if h=m is valid, we have to check if the value of the right node (= sum of frequency of elements >= m) is atleast m.
    If so, we can just move on and disregard the left side since per definition we only need to consider elements >= m now. 
    
    However if not, then we must move to [l,m-1]. since m-1 <= m, all elements >= m can be considered for the h index if our h is smaller than h. 
    Thus, we save an offset and every time we move to the left range, we add the right side to the offset. Now, instead of checking if 
    sum(right) >= m is true, we check sum(right)+offset >= m. 
    
    Runtime: O((n+q) log n)
*/
#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;

int MAXA = 2e5+4;

struct Node{
    int l = -1, r = -1, val = 0, left = -1, right = -1;
};

vector<Node> S;

int build(int n){
    int len = 1;
    while(len < n) len <<= 1;
    int offset = S.size()-1;
    int root = S.size();

    S.resize((2*len)+S.size());
    for(int i = 0; i < len; i++){
        S[i+len+offset] = Node{i,i+1}; 
    }

    for(int i = len-1; i > 0; i--){
        S[i+offset] = Node{S[(i*2)+offset].l,S[(i*2+1)+offset].r,0,(i*2)+offset,(i*2+1)+offset};
    }

    return root;
}

int query(int ql, int qr, int i){
    if(ql <= S[i].l && S[i].r <= qr) return S[i].val;
    if(S[i].r <= ql ||qr <= S[i].l) return 0;

    return query(ql,qr,S[i].left) + query(ql,qr,S[i].right);
}

int update(int p, int x, int i){
    int np = S.size();
    S.push_back(Node{});

    if(S[i].r-S[i].l == 1){
        S[np] = {S[i].l,S[i].r,S[i].val+x}; 
        return np;
    }

    int mid = (S[i].l+S[i].r)/2;
    if(p < mid){
        int nc = update(p,x,S[i].left);
        S[np] = Node{S[i].l,S[i].r,S[S[i].right].val + S[nc].val, nc, S[i].right};
    }else{
        int nc = update(p,x,S[i].right);
        S[np] = Node{S[i].l,S[i].r,S[S[i].left].val + S[nc].val, S[i].left, nc};
    }
    return np;
}

// i = left; j = right
int search(int off, int i, int j){
    if(S[i].r-S[i].l == 1) return S[i].l;

    int mid = (S[i].r+S[i].l)/2;
    int v = S[S[j].right].val-S[S[i].right].val;
    if(v+off >= mid){
        return search(off, S[i].right, S[j].right);
    }else{
        return search(off+v, S[i].left, S[j].left);
    }
}
int main(){
    int n,q;
    cin >> n >> q;
    vector<int> arr(n);

    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    vector<int> roots;
    roots.push_back(build(n+2));

    for(int i = 0; i < n; i++){
        int nr = update(min(arr[i],n+1), 1, roots.back());
        roots.push_back(nr);
    }
    while(q--){
        int l,r;
        cin >> l >> r; 
        cout << search(0,roots[l-1],roots[r]) << endl;
    }
}

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