Submission #976890

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
976890	2024-05-07T08:35:45 Z	Rux007	Martian DNA (BOI18_dna)	C++14	40 / 100	78 ms	5584 KB

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

        while(sol[a[st]] == 0 && st <= i)
            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

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	2 ms	2396 KB	Output is correct
4	Correct	2 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2496 KB	Output is correct
7	Correct	1 ms	2648 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2488 KB	Output is correct
11	Correct	1 ms	2392 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	2392 KB	Output is correct
2	Correct	23 ms	2652 KB	Output is correct
3	Correct	24 ms	2904 KB	Output is correct
4	Correct	24 ms	2908 KB	Output is correct
5	Correct	39 ms	3620 KB	Output is correct
6	Correct	22 ms	2652 KB	Output is correct
7	Correct	25 ms	2984 KB	Output is correct
8	Correct	41 ms	3676 KB	Output is correct
9	Correct	34 ms	3232 KB	Output is correct
10	Incorrect	21 ms	2652 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	2896 KB	Output is correct
2	Correct	60 ms	4436 KB	Output is correct
3	Correct	45 ms	4180 KB	Output is correct
4	Correct	27 ms	2652 KB	Output is correct
5	Correct	72 ms	5028 KB	Output is correct
6	Incorrect	77 ms	5584 KB	Output isn't correct
7	Halted	0 ms	0 KB	-