Submission #976882

#	Time	Username	Problem	Language	Result	Execution time	Memory
976882		Rux007	Martian DNA (BOI18_dna)	C++11	0 / 100	63 ms	2900 KiB

dna

#include <iostream>
#include <climits>

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 ++;
        }

        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: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32