Submission #1347069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347069		killerzaluu	Gift Boxes (EGOI25_giftboxes)	C++20	100 / 100	39 ms	6280 KiB

Main

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T, N;
    cin >> T >> N;

    int *a = new int[N];
    int *tot = new int[T]();
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        tot[a[i]]++;
    }

    int *cnt = new int[T]();
    int bad = 0;
    for (int x = 0; x < T; x++) {
        if (tot[x] >= 2) bad++;
    }

    int r = -1;
    int ansl = 0, ansr = N - 1;
    int best = N;

    for (int l = 0; l < N; l++) {
        while (r + 1 < N && bad > 0) {
            r++;
            int x = a[r];
            cnt[x]++;
            if (tot[x] >= 2 && cnt[x] == tot[x] - 1) bad--;
        }

        if (bad == 0) {
            if (r - l + 1 < best) {
                best = r - l + 1;
                ansl = l;
                ansr = r;
            }
        }

        int x = a[l];
        if (tot[x] >= 2 && cnt[x] == tot[x] - 1) bad++;
        cnt[x]--;
    }

    cout << ansl << ' ' << ansr << '\n';

    delete[] a;
    delete[] tot;
    delete[] cnt;
    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