제출 #1358986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358986		domi	Gift Boxes (EGOI25_giftboxes)	C++20	100 / 100	901 ms	39576 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 5e5;

using namespace std;

multiset<pair<int, int>> s;
int a[NMAX + 5], fr[NMAX + 5],  n, t;

inline void add(int i) {
    int x = a[i];
    if (fr[x] > 0)
        s.erase(make_pair(fr[x], x));
    ++fr[x];
    s.insert(make_pair(fr[x], x));
}

inline void rem(int i) {
    int x = a[i];
    s.erase(make_pair(fr[x], x));
    --fr[x];
    if (fr[x] > 0)
        s.insert(make_pair(fr[x], x));
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> t >> n;

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

    int r = 0, best = INT_MIN, bestL = -1, bestR = -1;
    for (int l = 1; l <= n; ++l) {
        while (l > r || (r + 1 <= n && s.rbegin()->fi != 1))
            rem(++r);

        if (!s.empty() && s.rbegin()->fi == 1 && sz(s) > best) {
            best = sz(s);
            tie(bestL, bestR) = make_pair(l, r);
        }
        else if (!s.empty() && s.rbegin()->fi == 1 && sz(s) == best && (r - l + 1) < (bestR - bestL + 1))
            tie(bestL, bestR) = make_pair(l, r);

        add(l);
    }

    cout << bestL - 1 << ' ' << bestR - 1 << '\n';
    return 0;
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 8 / 8
• 서브태스크 2: 11 / 11
• 서브태스크 3: 14 / 14
• 서브태스크 4: 21 / 21
• 서브태스크 5: 22 / 22
• 서브태스크 6: 24 / 24