Submission #723691

#	Time	Username	Problem	Language	Result	Execution time	Memory
723691		_martynas	Martian DNA (BOI18_dna)	C++11	100 / 100	140 ms	5252 KiB

dna

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back

using pii = pair<int, int>;
const int MXN = 2e5+5;

int n, k, r;
int A[MXN], req[MXN], tot[MXN], cnt[MXN];
int satisfied = 0;

int main() {
    cin >> n >> k >> r;
    for(int i = 0; i < n; i++) cin >> A[i];
    for(int i = 0; i < n; i++) tot[A[i]]++;
    for(int i = 0; i < r; i++) {
        int a, b; cin >> a >> b;
        req[a] = b;
        if(tot[a] < b) {
            cout << "impossible\n";
            return 0;
        }
    }
    auto add = [](int i) {
        cnt[A[i]]++;
        if(cnt[A[i]] == req[A[i]]) satisfied++;
    };
    auto del = [](int i) {
        if(cnt[A[i]] == req[A[i]]) satisfied--;
        cnt[A[i]]--;
    };
    auto ok = []() {
        return satisfied == r;
    };
    int lo = 1, hi = n;
    while(lo < hi) {
        int m = (lo+hi)/2;
        satisfied = 0;
        fill(cnt, cnt+k, 0);
        int i;
        for(i = 0; i < m; i++) add(i);
        bool f = false;
        if(ok()) f = true;
        for(; i < n; i++) {
            add(i), del(i-m);
            if(ok()) f = true;
        }
        if(f) {
            hi = m;
        }
        else {
            lo = m+1;
        }
    }
    cout << lo << "\n";
    return 0;
}

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