Submission #1096107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096107		ivaziva	Martian DNA (BOI18_dna)	C++14	0 / 100	51 ms	3360 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=0;i<k;i++) b[i]=INT_MAX;
    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 (b[a[r]]==INT_MAX) continue;
        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: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32