Submission #1096108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096108		ivaziva	Martian DNA (BOI18_dna)	C++14	100 / 100	60 ms	4436 KiB

dna

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200001

int n,k,rr;
int a[MAXN],b[MAXN],c[MAXN];

int main()
{
    cin>>n>>k>>rr;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=rr;i++) {int x,y;cin>>x>>y;b[x]=y;}
    int l=1,r=1;c[a[1]]=1;
    int brmanjih=rr;
    if (b[a[1]]==1) brmanjih--;
    int ans=INT_MAX;
    while (l<=r and r<=n)
    {
        if (brmanjih==0)
        {
            ans=min(ans,r-l+1);
            c[a[l]]--;l++;
            if (c[a[l-1]]<b[a[l-1]]) brmanjih++;
            continue;
        }
        if (r==n and brmanjih!=0) break;
        r++;c[a[r]]++;
        if (c[a[r]]<b[a[r]]) continue;
        if (c[a[r]]==b[a[r]]) {brmanjih--;continue;}
    }
    if (ans==INT_MAX) cout<<"impossible"<<endl;
    else cout<<ans<<endl;
}

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