Submission #1354974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354974		mxhrvs	Gift Boxes (EGOI25_giftboxes)	C++20	19 / 100	90 ms	19908 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll rx,lx,r,l;
void check() {
    if (rx - lx < r - l) {
        r = rx;
        l = lx;
    }
}
signed main(){
    ll t,n;
    cin >> t >> n;
    vector<ll> suff(n,-1),pref(n,-1),cnt(t,0);
    vector<ll> a(n,0);
    for(ll i = 0; i < n; i ++){
        cin >> a[i];
        if(pref[a[i]] == -1) pref[a[i]] = i;
        suff[a[i]] = i;
    }
    ll mxl = 0,mxr = n - 1;
    for(ll i = 0; i < n; i ++){
        if(cnt[a[i]] != 0) break;
        cnt[a[i]] ++;
        mxl ++;
    }
    cnt.resize(t+1,0);
    
    for(ll i = n - 1; i >= 0; i --){
        if(cnt[a[i]] != 0) break;
        cnt[a[i]] ++;
        mxr --;
    }
    r = n - 1;
    rx = mxr;
    for (ll i = 0; i < mxl; i++) {
        lx = i + 1;
        rx = max(rx, suff[a[i]]);
        check();
    }
    lx = mxl;
    for (ll i = n - 1; i > mxr; i--) {
        rx = i - 1;
        lx = min(lx, pref[a[i]]);
        check();
    }
    cout << l << " " << r << '\n';
}

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