Submission #536942

#	Time	Username	Problem	Language	Result	Execution time	Memory
536942		groshi	Martian DNA (BOI18_dna)	C++17	100 / 100	502 ms	20520 KiB

dna

#include<iostream>
#include<vector>
#include<map>
using namespace std;
map<int,int> zle;
map<int,int> mapka;
map<int,int> mam;
map<int,int>::iterator it,it2;
int t[1000000];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,k,r,x,y;
    cin>>n>>k>>r;
    for(int i=1;i<=n;i++)
        cin>>t[i];
    for(int i=1;i<=r;i++)
    {
        cin>>x>>y;
        mapka[x]=y;
        mam[x]=0;
        zle[x]=1;
    }
    int pocz=1;
    int wynik=1000000000;
    for(int i=1;i<=n;i++)
    {
        mam[t[i]]++;
        it=zle.find(t[i]);
        if(it!=zle.end())
        {
            it2=mapka.find(t[i]);
            if(mam[t[i]]>=it2->second)
                zle.erase(it);
        }
        it2=mapka.find(t[pocz]);
        while(pocz<=i && mam[t[pocz]]>it2->second)
        {
            mam[t[pocz]]--;
            pocz++;
            it2=mapka.find(t[pocz]);
        }
        if(zle.size()==0)
            wynik=min(wynik,i-pocz+1);
    }
    if(wynik==1000000000)
        cout<<"impossible";
    else cout<<wynik;
    return 0;
}

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