Submission #1317918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317918		nathako9n	Index (COCI21_index)	C++20	60 / 110	2596 ms	38368 KiB

index

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 200005;
int n,q,ar[N+3];
vector<int>seg[4*N+3];
void build(int i,int l,int r){
    if(l==r){
        seg[i].emplace_back(ar[l]);
        return;
    }
    int mid=l+(r-l)/2;
    build(i*2,l,mid); build(i*2+1,mid+1,r);
    seg[i].reserve(seg[i*2].size()+seg[i*2+1].size());
    merge(seg[i*2].begin(),seg[i*2].end(),seg[i*2+1].begin(),seg[i*2+1].end(),back_inserter(seg[i]));
}
int que(int i,int l,int r,int ql,int qr,int x){
    if(r<ql||l>qr)return 0;
    else if(l>=ql&&r<=qr){
        int it=lower_bound(seg[i].begin(),seg[i].end(),x)-seg[i].begin();
        return seg[i].size()-it;
    }
    int mid=l+(r-l)/2;
    return que(i*2,l,mid,ql,qr,x)+que(i*2+1,mid+1,r,ql,qr,x);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
    }
    build(1,1,n);
    while(q--){
        int L,R;cin>>L>>R;
        int l=1,r=R-L+1,ans=0;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(que(1,1,n,L,R,mid)>=mid){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
}


/*



*/

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