Submission #1356622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1356622		mahriban	Gift Boxes (EGOI25_giftboxes)	C++20	100 / 100	83 ms	6288 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int fr[500009], ls[500009];
bool vis[500009];
int a[500009];
int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i ++){
        cin >> a[i];
        if (!fr[a[i]])fr[a[i]] = i;
        ls[a[i]] = i;
    }
    int r = -1, l = 0;
    for (int i = m; i >= 1; i --){
        if (ls[a[i]] != i){r = i;break;}
    }
    int mx = 0, ansl = 0, ansr = 0;
    for (l = 1; l <= n; l ++){
        if (fr[a[l]] != l)break;
        r = max(r, ls[a[l]]);
        if (mx < m - r + l){
            mx = m - r + l;
            ansl = l + 1;
            ansr = r;
        }
    }
    for (int i = 1; i <= m; i ++){
        if (fr[a[i]] != i){l = i; break;}
    }
    for (r = m; r >= 1; r --){
        if (ls[a[r]] != r)break;
        l = min(l, fr[a[r]]);
        if (mx < m - r + l){
            mx = m - r + l;
            ansl = l;
            ansr = r - 1;        
        }
    }
    cout << ansl - 1 << ' ' << ansr - 1 << 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