제출 #1334292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1334292		ezzzay	Gift Boxes (EGOI25_giftboxes)	C++20	36 / 100	2095 ms	25464 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define ll long long
const int N=1e6;
int a[N];
int fo[N];
signed main(){
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(fo[a[i]]==0)fo[a[i]]=i;
    }
    set<int>ts;int R=0;
    for(int i=n;i>=1;i--){
        ts.insert(a[i]);
        if(ts.size()!=n-i+1){
            R=i;
            break;
        }
    }
    set<int>st;
    pair<int,int>mx={1e9,0};
    for(int i=0;i<=n;i++){
        if(i)st.insert(a[i]);
        if(st.size()<i)break;
        int lo=max(i+1,R+1),hi=n;
        while(hi>=lo){
            int mid=(hi+lo)/2;
            bool u=1;
            for(int j=mid;j<=n;j++){
                if(fo[a[j]]<=i )u=0;
            }
            if(u)hi=mid-1;
            else lo=mid+1;
            // first occurence ni i aas ers ih baih ystoi
        }
        mx=min(mx,{hi-i,i});
    }
    cout<<mx.ss<<" "<<mx.ff+mx.ss-1<<endl;
    
}

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