Submission #1013755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013755		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	62 ms	10032 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define ll long long
#define int long long
const long long inf=1e18;
const int MOD=998244353;
const int N=3e5+5;
int req[N],am[N];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,k,r; cin>>n>>k>>r;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    set<int> bad;
    for(int i=0;i<r;i++){
        int x,y; cin>>x>>y;
        bad.insert(x);
        req[x]=y;
    }
    int ans=inf,l=0;
    for(int i=0;i<n;i++){
        am[a[i]]++;
        if(am[a[i]]==req[a[i]]){
            bad.erase(a[i]);
        }
        while(bad.size()==0){
            if(am[a[l]]<=req[a[l]])break;
            am[a[l]]--;
            l++;
        }
        if(bad.size()==0){
            ans=min(ans,i-l+1);
        }
    }
    if(ans==inf)cout<<"impossible";
    else cout<<ans;
}

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