Submission #1013796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013796		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	26 ms	8592 KiB

dna

//
//  main1.cpp
//  problem1
//
//  Created by Essa Almousa on 2030 / 01/ 01 AD.
//

#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
using ll = long long;
#define pb push_back
#define pF first
#define pS second
#define SP <<" "<<
const ll N = 3e5;
ll a[N], req[N], frq[N], ans1[N];
int main() {
    ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    ll n, k, q;
    cin>>n>>k>>q;
    for (int i=0; i<n; i++) {
        cin>>a[i];
        ans1[a[i]] = 1;
    }
    for (int i=0; i<q; i++) {
        ll x, y; cin>>x>>y;
        req[x] = y;
        ans1[x] = 0;
    }
    ll mn = INT_MAX, l = 0, r = -1;
    ll ans = q;
    while (r <= n-1 && l <= n-1) {
        if (ans == 0) {
            mn = min(mn, r-l+1);
        }
        if (ans != 0) {
            r++;
            if (r >= n) break;
            frq[a[r]]++;
            if (req[a[r]] <= frq[a[r]]) {
                if (ans1[a[r]] == 0) {
                    ans1[a[r]] = 1;
                    ans--;
                }
            }
        }
        else if (ans == 0) {
            frq[a[l]]--;
            if (req[a[l]] > frq[a[l]]) {
                if (ans1[a[l]] == 1) {
                    ans1[a[l]] = 0;
                    ans++;
                }
            }
            l++;
        }
    }
    if (ans == 0) {
        mn = min(mn, r-l+1);
    }
    if (mn == INT_MAX) cout << "impossible";
    else cout << mn;
}

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