Submission #1368553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368553		hahaha	Gift Boxes (EGOI25_giftboxes)	C++20	100 / 100	86 ms	12284 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int N=5e5+7;
int n,t;
vector<int>a;
vector<int> temp;
int cnt[N];
int dub;
int f[N];
signed main(){
    cin>>t>>n;
    int mx=0;
    for(int i=0; i<n; i++){
        int x;
        cin>>x;
        a.pb(x);
        if (cnt[x]==1)dub++;
        cnt[x]++;
    }
    int l=0;
    int r=0;
    int ans=N, ansl, ansr;
    int gstdif=0;
    int stpr=-1;
    while (gstdif<dub&&r<n) {
        f[a[r]]++;
        if (f[a[r]]==cnt[a[r]]-1 && cnt[a[r]]>1) gstdif++;
        if (f[a[r]]>1&& stpr==-1) stpr=r;
        r++;
    }
    if (stpr==-1)stpr=r;
    r--;
    if(ans>r-l+1) {
        ans=r-l+1;
        ansl=l;
        ansr=r;
    };

    while (l<stpr) {
        l++;
        f[a[l-1]]--;
        while(f[a[l-1]]<cnt[a[l-1]]-1&&r<n-1){
            r++;
            f[a[r]]++;
        }
        if(ans>r-l+1) {
            ans=r-l+1;
            ansl=l;
            ansr=r;
        }
    }
    cout<<ansl<<" "<<ansr<<endl;

}

• 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