제출 #1204542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204542		Newtonabc	Index (COCI21_index)	C++20	110 / 110	1427 ms	77140 KiB

index

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
const int M=2e5+10;
struct node{
    int l,r;
    long long val;
}s[N];
vector<int> pos[M],df;
int arr[M],cnt=1,root[M];
int clone(int idx){s[++cnt]=s[idx]; return cnt;}
int build(int l,int r,int idx){
    if(l==r){
        s[idx]={0,0,0};
        return idx;
    }
    int m=(l+r)/2;
    s[idx].l=build(l,m,++cnt);
    s[idx].r=build(m+1,r,++cnt);
    s[idx].val=s[s[idx].l].val+s[s[idx].r].val;
    return idx;
}
int update(int l,int r,int idx,int a,int b){
    int now=clone(idx);
    if(l==r){
        s[now].val=b;
        return now;
    }
    int m=(l+r)/2;
    if(a<=m) s[now].l=update(l,m,s[idx].l,a,b);
    else s[now].r=update(m+1,r,s[idx].r,a,b);
    s[now].val=s[s[now].l].val+s[s[now].r].val;
    return now;
}
int query(int l,int r,int idx,int a,int b){
    if(a>r || b<l) return 0;
    if(a<=l && b>=r) return s[idx].val;
    int m=(l+r)/2;
    return query(l,m,s[idx].l,a,b)+query(m+1,r,s[idx].r,a,b);
}
int main(){
    int n,q;
    cin>>n >>q;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        pos[arr[i]].push_back(i);
        df.push_back(arr[i]);
    }
    sort(df.begin(),df.end());
    df.erase(unique(df.begin(),df.end()),df.end());
    int rt=build(1,n,1);
    reverse(df.begin(),df.end());
    for(int i=0;i<df.size();i++){
        //put df[i] in to the segment tree then update root[i] be the segment tree version i
        for(auto ind:pos[df[i]]){
            rt=update(1,n,rt,ind,1);
            //cout<<"update" <<df[i] <<" " <<ind <<"\n";
        }
        root[i]=rt;
    }
    // for(int i=0;i<df.size();i++){
    //     for(int j=1;j<=n;j++){
    //         cout<<query(1,n,root[i],j,j) <<" ";
    //     }
    //     cout<<"\n";
    // }
    int sz=df.size();
    while(q--){
        int a,b;
        cin>>a >>b;
        int l=0,r=2e5;
        while(l<r){
            int mid=(l+r+1)/2;
            int indl=0,indr=sz-1;
            if(mid>df[0]){
                r=mid-1;
                continue;
            }
            while(indl<indr){
                int indm=(indl+indr+1)/2;
                if(df[indm]>=mid) indl=indm;
                else indr=indm-1;
            }
            int ind=indl;
            int fd=query(1,n,root[ind],a,b);
            //cout<<mid <<" " <<fd <<"\n";
            if(fd>=mid) l=mid;
            else r=mid-1;
        }
        cout<<l <<"\n";
    }
}

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