Submission #837171

#	Time	Username	Problem	Language	Result	Execution time	Memory
837171		1075508020060209tc	Martian DNA (BOI18_dna)	C++14	100 / 100	77 ms	8136 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;int K;int m;

int ar[1000006];
int freq[1000006];
int isin[1000006];
int nd[1000006];
int ans;
int tot;

void ad(int v){
freq[v]++;
if(isin[v]&&nd[v]==freq[v]){
    tot++;
}
}
void del(int v){
if(isin[v]&&nd[v]==freq[v]){
    tot--;
}
freq[v]--;
}

signed main() {
cin>>n>>K>>m;
for(int i=1;i<=n;i++){
    cin>>ar[i];
}
for(int i=1;i<=m;i++){
    int pl;int v;
     cin>>pl>>v;
    isin[pl]=1;
    nd[pl]=v;
}
ans=n+1;
tot=0;
int rit=0;
for(int i=1;i<=n;i++){
    while(tot<m&&rit<=n-1){ad(ar[++rit]);}
    if(tot==m){
        ans=min(ans,rit-i+1);
    }
   // cout<<i<<" "<<rit<<" "<<tot<<endl;
    del(ar[i]);

}
if(ans==n+1){
    cout<<"impossible\n";return 0;
}
cout<<ans<<endl;
}

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