Submission #1308702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308702		hom84287	Index (COCI21_index)	C++20	110 / 110	200 ms	11016 KiB

index

#include<bits/stdc++.h>
using namespace std ;
#define ff first
#define ss second 
#define int long long
typedef long long ll ;
typedef pair<int,int> pii ;

const int maxn = 2e5+12;
const int maxk = 110 ; 
const int maxlg = 25 ;
const int sq = 320 ;  
const int MOD = 998244353;
const int INF = 1e17 ;

int n,q,cnt[maxn],a[maxn],h,uph,ans[maxn] ;
struct qee{
    int l,r,num ; 
}qe[maxn] ;
bool cmp(qee A , qee B){
    if(A.l/sq==B.l/sq){
        if((A.l/sq)&1)
            return A.r>B.r ;
        return A.r<B.r ;
    }
    return A.l<B.l ;
}
void solve(){
    cin>>n>>q ;
    for(int i=1 ; i<=n ; i++)
        cin>>a[i] ; 
    for(int i=1 ; i<=q ;i++){
        cin>>qe[i].l>>qe[i].r ;
        qe[i].num=i ; 
    }
    sort(qe,qe+q+1,cmp) ;
    int l=1 , r=1 ;
    cnt[a[1]]++  ;
    h=1 ; uph=1 ;
    for(int i=1 ; i<=q ; i++){
        while(r<qe[i].r){
            r++ ;
            cnt[a[r]]++ ; 
            if(a[r]>=h) uph++ ; 
            if(uph-cnt[h]>=h+1){
                 uph-=cnt[h] ; h++ ;
            } 
        }
        while(qe[i].l<l){
            l-- ;
            cnt[a[l]]++ ; 
            if(a[l]>=h) uph++ ;
            if(uph-cnt[h]>=h+1){
                 uph-=cnt[h] ; h++ ;
            }
        }
        while(r>qe[i].r){
            cnt[a[r]]-- ; 
            if(a[r]>=h) uph-- ;
            if(uph<h){
                 uph+=cnt[h-1] ; h-- ;
            }
            r-- ; 
        }
        while(l<qe[i].l){
            cnt[a[l]]-- ; 
            if(a[l]>=h) uph-- ;
            if(uph<h){
                 uph+=cnt[h-1] ; h-- ;
            }
            l++ ;
        } 
        ans[qe[i].num]=h ;
    }  
    for(int i=1 ; i<=q ; i++)
        cout<<ans[i]<<'\n' ;   
}
signed main(){
    ios::sync_with_stdio(0) ;
    cin.tie(0) ; cout.tie(0) ;
    solve() ; 
}

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