Submission #320905

#	Time	Username	Problem	Language	Result	Execution time	Memory
320905		gustason	Martian DNA (BOI18_dna)	C++14	100 / 100	184 ms	24032 KiB

dna

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 5;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r, q;
    cin >> n >> r >> q;

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

    vector<int> need(r+1, INF), cnt(r+1, 0);
    for(int i = 0; i < q; i++) {
        int b;
        cin >> b;
        cin >> need[b];
    }

    int good = 0, ans = INF;
    set<int> begins, ends;
    vector<int> pos[r+1];
    for(int i = 0; i < n; i++) {
        int c = dna[i];
        cnt[c]++;
        pos[c].push_back(i);
        if (cnt[c] == need[c]) {
            good++;
            begins.insert(pos[c][0]);
            ends.insert(pos[c][need[c]-1]);
        }
        if (cnt[c] > need[c]) {
            begins.erase(pos[c][cnt[c]-need[c]-1]);
            ends.erase(pos[c][cnt[c]-2]);
            begins.insert(pos[c][cnt[c]-need[c]]);
            ends.insert(pos[c][cnt[c]-1]);
        }
        if (good == q) {
            ans = min(ans, *ends.rbegin() - *begins.begin() + 1);
        }
    }

    if (ans == INF) {
        cout << "impossible";
    } else {
        cout << ans << "\n";
    }

//    cout << good << "\n";
//    for(auto i : ends) {
//        cout << i << "\n";
//    }
    return 0;
}
//~ check for overflows

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32