Submission #940491

#	Time	Username	Problem	Language	Result	Execution time	Memory
940491		irmuun	Martian DNA (BOI18_dna)	C++17	100 / 100	122 ms	30556 KiB

dna

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,k,r;
    cin>>n>>k>>r;
    int a[n];
    set<int>st[k];
    for(int i=0;i<k;i++){
        st[i].insert(n);
    }
    for(int i=0;i<n;i++){
        cin>>a[i];
        st[a[i]].insert(i);
    }
    vector<bool>need(k,0);
    int b[r],q[r];
    int R=0;
    for(int i=0;i<r;i++){
        cin>>b[i]>>q[i];
        need[b[i]]=true;
        if((int)st[b[i]].size()-1<q[i]){
            cout<<"impossible";
            return 0;
        }
        q[i]--;
        R=max(R,*st[b[i]].begin());
        while(q[i]--){
            st[b[i]].erase(st[b[i]].begin());
            R=max(R,*st[b[i]].begin());
        }
    }
    int ans=n;
    for(int i=0;i<n;i++){
        if(R<n) ans=min(ans,R-i+1);
        if(need[a[i]]==true){
            if(!st[a[i]].empty()) st[a[i]].erase(st[a[i]].begin());
            if(!st[a[i]].empty()) R=max(R,*st[a[i]].begin());
        }
    }
    cout<<ans;
}

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