Submission #1221757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221757		m5588ohammed	Index (COCI21_index)	C++20	110 / 110	725 ms	134308 KiB

index

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mod 1000000007
#define int long long
int n,q;
int arr[200001];
struct node{
    node *Left,*Right;
    int sum=0;
};
node *rt[200001];
void set_initially(int l1,int r1,node *curr){
    if(l1==r1) return;
    curr->Left=new node();
    curr->Right=new node();
    set_initially(l1,(l1+r1)/2,curr->Left);
    set_initially((l1+r1)/2+1,r1,curr->Right);
    return;
}
int solve(int l1,int r1,int l,int r,node *currL,node *currR){
    if(l1>r||l>r1) return 0;
    if(l<=l1&&r1<=r) return currR->sum - currL->sum;
    return solve(l1,(l1+r1)/2,l,r,currL->Left,currR->Left)+solve((l1+r1)/2+1,r1,l,r,currL->Right,currR->Right);
}
node* update(int l1,int r1,int x,node *curr){
    if(l1==r1){
        node *nw=new node();
        nw->sum=curr->sum+1;
        return nw;
    }
    node *nw=new node();
    if(x<=(l1+r1)/2){
        nw->Right=curr->Right;
        nw->Left=update(l1,(l1+r1)/2,x,curr->Left);
    }
    else{
        nw->Left=curr->Left;
        nw->Right=update((l1+r1)/2+1,r1,x,curr->Right);
    }
    nw->sum=nw->Left->sum+nw->Right->sum;
    return nw;        
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    rt[0]=new node();
    set_initially(0,2e5,rt[0]);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        rt[i]=update(0,2e5,arr[i],rt[i-1]);
    }
    //cout<<solve(1,2e5,3,2e5,rt[0],rt[1])<<endl;
    while(q--){
        int i,j;
        cin>>i>>j;
        i--;
        int l=0,r=2e5,ans=0;
        while(l<=r){
            int mid=(l+r)/2;
            if(solve(0,2e5,mid,2e5,rt[i],rt[j])>=mid){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}
//g++ -std=c++17 template.cpp -o executable.exe

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