Submission #976931

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
976931	2024-05-07T09:21:30 Z	Rux007	Martian DNA (BOI18_dna)	C++14	40 / 100	89 ms	7420 KB

dna

#include <iostream>
#include <climits>

using namespace std;

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

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

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

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

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

    for(long long 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	2 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	2 ms	2488 KB	Output is correct
4	Correct	3 ms	2396 KB	Output is correct
5	Correct	2 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2392 KB	Output is correct
9	Correct	1 ms	2392 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	2392 KB	Output is correct
3	Correct	2 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	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2392 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 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	2392 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4700 KB	Output is correct
2	Correct	23 ms	4700 KB	Output is correct
3	Correct	23 ms	4952 KB	Output is correct
4	Correct	23 ms	4956 KB	Output is correct
5	Correct	40 ms	5152 KB	Output is correct
6	Correct	22 ms	4700 KB	Output is correct
7	Correct	26 ms	4956 KB	Output is correct
8	Correct	45 ms	5536 KB	Output is correct
9	Correct	37 ms	5616 KB	Output is correct
10	Incorrect	24 ms	4700 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	6224 KB	Output is correct
2	Correct	59 ms	5980 KB	Output is correct
3	Correct	51 ms	5956 KB	Output is correct
4	Correct	28 ms	4696 KB	Output is correct
5	Correct	89 ms	6476 KB	Output is correct
6	Incorrect	75 ms	7420 KB	Output isn't correct
7	Halted	0 ms	0 KB	-