Submission #976973

#	Time	Username	Problem	Language	Result	Execution time	Memory
976973		Rux007	Martian DNA (BOI18_dna)	C++14	100 / 100	85 ms	4912 KiB

dna

#include <iostream>

using namespace std;

const int nmax = 200005;
int sol[nmax], fr[nmax], a[nmax], n, k, r, gasit[nmax];

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

    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    for(int i = 1; i <= r; i ++)
    {
        int x, y; cin >> x >> y;
        sol[x] = y;
    }

    int st = 1, mini = n + 1, ok = 0;

    for(int i = 1; i <= n; i ++)
    {
        fr[a[i]] ++;
        while(fr[a[i]] > sol[a[i]])
        {
            if(fr[a[st]] <= sol[a[st]])
                break;
            else
                fr[a[st]] --;
            st ++;
        }

        while(st <= i)
        {
            if(sol[a[st]] == 0 || fr[a[st]] > sol[a[st]])
                fr[a[st ++]] --;

            else
                break;
        }

        if(sol[a[i]] > 0 && fr[a[i]] == sol[a[i]] && !gasit[a[i]])
            ok ++, gasit[a[i]] = 1;

        if(ok == r)
            mini = min(mini, i - st + 1);
    }

    if(mini <= n)
        cout << mini;
    else
        cout << "impossible";
    return 0;
}

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