Submission #1189414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189414		AlgorithmWarrior	Martian DNA (BOI18_dna)	C++20	100 / 100	90 ms	9544 KiB

dna

#include <bits/stdc++.h>

using namespace std;

int const INF=1000000000;
int const MAX=200005;
int n,alsz,req;
int v[MAX];
int nec[MAX];
int lstap[MAX];
int urm[MAX];
int cnt[MAX];
int capat[MAX];

void read(){
    cin>>n>>alsz>>req;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
    for(i=1;i<=req;++i){
        int lit,nr;
        cin>>lit>>nr;
        nec[lit]=nr;
    }
}

void precalc(){
    int i;
    for(i=n;i;--i){
        urm[i]=lstap[v[i]];
        lstap[v[i]]=i;
    }
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

int solve(){
    int i;
    int ok=0;
    for(i=1;i<=n && ok<req;++i){
        ++cnt[v[i]];
        if(cnt[v[i]]==nec[v[i]])
            ++ok;
    }
    int ans;
    if(ok<req)
        ans=INF;
    else{
        set<int>beg;
        int lt;
        for(lt=0;lt<alsz;++lt)
            if(nec[lt]){
                capat[lt]=lstap[lt];
                while(cnt[lt]>nec[lt]){
                    capat[lt]=urm[capat[lt]];
                    --cnt[lt];
                }
                beg.insert(capat[lt]);
            }
        ans=i-*beg.begin();
        for(;i<=n;++i){
            if(nec[v[i]]){
                beg.erase(capat[v[i]]);
                capat[v[i]]=urm[capat[v[i]]];
                beg.insert(capat[v[i]]);
            }
            minself(ans,i-*beg.begin()+1);
        }
    }
    return ans;
}

void write(int ans){
    if(ans<INF)
        cout<<ans;
    else
        cout<<"impossible";
}

int main()
{
    read();
    precalc();
    write(solve());
    return 0;
}

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