Submission #891029

#	Time	Username	Problem	Language	Result	Execution time	Memory
891029		Fibohyan	Martian DNA (BOI18_dna)	C++17	100 / 100	215 ms	14420 KiB

dna

#include <bits/stdc++.h> 
using namespace std;
#define int long long
int n,k,r,z,o=LLONG_MAX;
map<int,int>m;
signed main(){ 
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cin>>n>>k>>r;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<r;i++){
        int smth,idk;
        cin>>smth>>idk;
        m[smth]=idk;
    }
    int x=0,j=r,z=o;
    for(int l=0;l<n;l++){
        while(j>0&&x<n){
            m[a[x]]--;
            if(m[a[x]]==0){
                j--;
            }
            x++;
        }
        if(j==0){
            o=min(o,x-l);
        }
        m[a[l]]++;
        if(m[a[l]]==1){
            j++;
        }

    }
    if(o==z){
        cout<<"impossible";
        return 0;
    }
    cout<<o;

    
    
    
    
    return 0;}

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