Submission #676901

#	Time	Username	Problem	Language	Result	Execution time	Memory
676901		KKT89	Martian DNA (BOI18_dna)	C++17	100 / 100	31 ms	4492 KiB

dna

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myrand(ll B){
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,k,q; cin >> n >> k >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> b(k);
    for (int i = 0; i < q; ++i) {
        int x,y; cin >> x >> y;
        b[x] = y;
    }
    vector<int> c(k);
    int cnt = 0;
    for (int i = 0; i < k; ++i) {
        if(c[i] >= b[i]) cnt++;
    }
    int res = n+1;
    int r = 0;
    for (int l = 0; l < n; ++l) {
        while(r < n and cnt < k){
            c[a[r]]++;
            if(c[a[r]] == b[a[r]]) cnt++;
            r++;
        }
        if(cnt == k){
            res = min(res, r-l);
        }
        if(c[a[l]] == b[a[l]]) cnt--;
        c[a[l]]--;
    }
    if(res == n+1){
        cout << "impossible" << endl;
    }
    else{
        cout << res << endl;
    }
}

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