Submission #976958

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
976958	2024-05-07T09:44:31 Z	Rux007	Martian DNA (BOI18_dna)	C++14	40 / 100	72 ms	7852 KB

dna

#include <iostream>
#include <climits>

using namespace std;

const int nmax = 2000005;
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	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct

Subtask #2

24.0 / 24.0

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

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	6492 KB	Output is correct
2	Correct	23 ms	6492 KB	Output is correct
3	Correct	23 ms	6492 KB	Output is correct
4	Correct	23 ms	6480 KB	Output is correct
5	Correct	40 ms	6740 KB	Output is correct
6	Correct	21 ms	6492 KB	Output is correct
7	Correct	25 ms	6592 KB	Output is correct
8	Correct	45 ms	7336 KB	Output is correct
9	Correct	35 ms	6480 KB	Output is correct
10	Incorrect	25 ms	6484 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	7084 KB	Output is correct
2	Correct	57 ms	6996 KB	Output is correct
3	Correct	46 ms	6992 KB	Output is correct
4	Correct	23 ms	6492 KB	Output is correct
5	Correct	71 ms	6836 KB	Output is correct
6	Incorrect	72 ms	7852 KB	Output isn't correct
7	Halted	0 ms	0 KB	-