Submission #1157945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157945		dosts	Martian DNA (BOI18_dna)	C++20	100 / 100	24 ms	4936 KiB

dna

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 2e18,N = 5e5+1,MOD =  1e9+7;

void solve() {
    int n,k,q;
    cin >> n >> k >> q;
    vi need(k,0);
    vi a(n);
    for (int i=0;i<n;i++) cin >> a[i];
    int sm = 0;
    for (int i=0;i<q;i++) {
        int b,c;
        cin >> b >> c;
        sm+=c;
        need[b] = c;
    }
    int amass = 0;
    vi have(k,0);
    int ptr = -1;
    int ans = n+1;
    for (int i = 0;i<n;i++) {
        while (ptr < n-1 && amass != sm) {
            if (have[a[ptr+1]] < need[a[ptr+1]]) amass++;
            have[a[ptr+1]]++;
            ptr++;
        }
        if (sm == amass) ans = min(ans,ptr-i+1);
        if (have[a[i]] <= need[a[i]]) amass--;
        have[a[i]]--;
    }
    if (ans == n+1) cout << "impossible\n";
    else cout << ans << '\n';
}


int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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