제출 #1359991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1359991		domi	Martian DNA (BOI18_dna)	C++20	100 / 100	182 ms	11144 KiB

dna

#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 = 2e5;

using namespace std;

multiset<pair<int, int>> s;
int a[NMAX + 5], req[NMAX + 5], remaining[NMAX + 5], n, k, r;

void add(int i) {
    int x = a[i];
    if (!req[x]) return;

    s.erase({remaining[x], x});
    --remaining[x];
    s.insert({remaining[x], x});
}

void rem(int i) {
    int x = a[i];
    if (!req[x]) return;

    s.erase({remaining[x], x});
    ++remaining[x];
    s.insert({remaining[x], x});
}

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

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

    for (int i = 0, type, cate; i < r; ++i) {
        cin >> type >> cate;
        ++type;
        req[type] = true;
        remaining[type] = cate;
        s.insert({cate, type});
    }

    int ans = INT_MAX, r = 0;
    for (int l = 1; l <= n; ++l) {
        while (r < l || (r + 1 <= n && s.rbegin()->fi > 0))
            add(++r);

        if (s.rbegin()->fi <= 0)
            ans = min(ans, (r - l + 1));
        rem(l);
    }

    if (ans == INT_MAX) {
        cout << "impossible\n";
        exit(0);
    }

    cout << ans << '\n';
    return 0;
}

• 서브태스크 1: 16 / 16
• 서브태스크 2: 24 / 24
• 서브태스크 3: 28 / 28
• 서브태스크 4: 32 / 32