Submission #1363335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363335		liptonek	Gift Boxes (EGOI25_giftboxes)	C++20	100 / 100	35 ms	10156 KiB

Main

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t,n;
    cin>>t>>n;

    vector<int> a(n);
    vector<int> l(t,-1);
    vector<int> r(t,-1);

    for(int i=0; i<n; i++)
    {
        cin>>a[i];

        if(l[a[i]]==-1)
        {
            l[a[i]]=i;
        }

        r[a[i]]=i;
    }

    int p=0;

    vector<bool> seen(t,false);

    while(p<n && !seen[a[p]])
    {
        seen[a[p]]=true;

        p++;
    }

    int s=n;

    fill(seen.begin(),seen.end(),false);

    while(s>0 && !seen[a[s-1]])
    {
        s--;

        seen[a[s]]=true;
    }

    vector<int> M(p+1);

    M[0]=0;

    for(int i=1; i<=p; i++)
    {
        M[i]=max(M[i-1],r[a[i-1]]+1);
    }

    vector<int> m(n+1);

    m[n]=n;

    for(int j=n-1; j>=s; j--)
    {
        m[j]=min(m[j+1],l[a[j]]);
    }

    int bl=-1;
    int br=-1;
    int len=n+1;
    int j=s;

    for(int i=0; i<=p; i++)
    {
        int jn=max({s,i+1,m[i]});

        if(j<jn)
        {
            j=jn;
        }

        while(j<n && m[j]<i)
        {
            j++;
        }

        if(j<=n && m[j]>=i)
        {
            if(j-i<len)
            {
                len=j-i;
                bl=i;
                br=j-1;
            }
        }
    }

    cout<<bl<<" "<<br<<endl;

    return 0;
}

• 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