Submission #1333871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333871		eri16	Gift Boxes (EGOI25_giftboxes)	C++20	100 / 100	131 ms	12080 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main(){
    ll T,N;
    
    cin>>T>>N;
    
    vector <ll> v(N);
    vector <ll> freq(T,0);    
    
    for (int i=0; i<N; i++){cin>>v[i];freq[v[i]]++;}

    ll sm=0;

    for (int i=0; i<T; i++){if (freq[i]>1){sm++;}}
    
    vector<ll> windowfreq(T, 0);

    ll l=0;
    ll bestLen=LLONG_MAX;
    ll bl=0, br=-1;

    for(ll r=0; r<N; r++){
        ll x=v[r];
        windowfreq[x]++;

        if(freq[x]-windowfreq[x]==1){
            sm--; 
        }

        while(sm==0){
            if(r-l+1<bestLen){
                bestLen=r-l+1;
                bl=l;
                br=r;
            }

            ll y=v[l];
            windowfreq[y]--;

            if(freq[y]-windowfreq[y]==2){
                sm++;
            }
            l++;
        }
    }
    
    cout<<bl<<' '<<br<<"\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 24 / 24