Submission #876528

#	Time	Username	Problem	Language	Result	Execution time	Memory
876528		MasterTaster	Martian DNA (BOI18_dna)	C++14	100 / 100	107 ms	24316 KiB

dna

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 200010

using namespace std;

int n, k, r, a[MAXN];
set<int> svi[MAXN];
set<int>::iterator it[MAXN];
int kolko[MAXN], ress;

int main() {
    cin>>n>>k>>r;

    for (int i=0; i<n; i++)
    {
        cin>>a[i];
        svi[a[i]].insert(i);
    }
    for (int i=0; i<r; i++)
    {
        int b, q; cin>>b>>q;
        kolko[b]=q;
    }

    int r=-1;
    for (int i=0; i<n; i++) {
        if (kolko[i] == 0) continue;
        int pom = kolko[i];
        it[i] = svi[i].begin();
        while (pom-1)
        {
            //cout<<i<<" "<<*it[i]<<endl;
            pom--;
            it[i]++;
            if (it[i]==svi[i].end()) { cout<<"impossible"; exit(0); }
        }
        //cout<<i<<" "<<*it[i]<<endl;
        r=max(r, *(it[i]));
    }
    //cout<<"ee "<<r<<endl;

    ress=r+1;
    for (int i=0; i<n; i++)
    {
        if (kolko[a[i]]==0) { ress=min(ress, r-i); continue; }
        it[a[i]]++;
        if (it[a[i]]==svi[a[i]].end()) break;
        r=max(r, *(it[a[i]]));
        ress=min(ress, r-i);
    }
    cout<<ress;
}

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