Submission #1310453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310453		Samakahhh	Martian DNA (BOI18_dna)	C++20	100 / 100	513 ms	29272 KiB

dna

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll ;
map<ll,ll>req,fa;
set<ll>st;
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ;
    ll n,k,qq;
    cin >>n>>k>>qq;
    ll a[n];
    for(ll i=0;i<n;i++){
        cin >>a[i];
    }
    while(qq--){
    ll x,y;
    cin >>x>>y;
    req[x]=y;
    st.insert(x) ;

    }

    ll l=0,r=0,mn=1e9;

    while(l < n){
        while(r<n && !st.empty()){
            fa[a[r]]++;
            if(fa[a[r]]==req[a[r]]){
                st.erase(a[r]);
            }
            r++;
        }
        if(st.empty())
            mn=min(mn,r-l);
//        cout << l << " " << r << endl ;
        fa[a[l]]--;
        if(fa[a[l]] < req[a[l]])
            st.insert(a[l]);
        l++;
    }
    if(mn!=1e9)
    cout <<mn<<endl;
    else{
        cout <<"impossible"<<endl;
    }
    return 0;
}

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