| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 976973 |
2024-05-07T09:52:11 Z |
Rux007 |
Martian DNA (BOI18_dna) |
C++14 |
|
85 ms |
4912 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 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 |
2492 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 |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 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 |
2 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2492 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 |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2392 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 |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
24 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
23 ms |
2908 KB |
Output is correct |
| 4 |
Correct |
22 ms |
2900 KB |
Output is correct |
| 5 |
Correct |
41 ms |
3244 KB |
Output is correct |
| 6 |
Correct |
21 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
25 ms |
2904 KB |
Output is correct |
| 8 |
Correct |
42 ms |
3468 KB |
Output is correct |
| 9 |
Correct |
34 ms |
3180 KB |
Output is correct |
| 10 |
Correct |
22 ms |
2652 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 |
2 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2488 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
4176 KB |
Output is correct |
| 2 |
Correct |
57 ms |
3984 KB |
Output is correct |
| 3 |
Correct |
46 ms |
3920 KB |
Output is correct |
| 4 |
Correct |
24 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
71 ms |
4252 KB |
Output is correct |
| 6 |
Correct |
85 ms |
4912 KB |
Output is correct |
| 7 |
Correct |
37 ms |
3364 KB |
Output is correct |
| 8 |
Correct |
47 ms |
3616 KB |
Output is correct |
| 9 |
Correct |
21 ms |
2648 KB |
Output is correct |
| 10 |
Correct |
24 ms |
2652 KB |
Output is correct |
| 11 |
Correct |
24 ms |
2796 KB |
Output is correct |
| 12 |
Correct |
22 ms |
2652 KB |
Output is correct |
| 13 |
Correct |
47 ms |
3496 KB |
Output is correct |
| 14 |
Correct |
21 ms |
2856 KB |
Output is correct |
| 15 |
Correct |
30 ms |
3164 KB |
Output is correct |
| 16 |
Correct |
41 ms |
3820 KB |
Output is correct |
| 17 |
Correct |
34 ms |
3420 KB |
Output is correct |
| 18 |
Correct |
28 ms |
2652 KB |
Output is correct |
| 19 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2472 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2496 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 33 |
Correct |
1 ms |
2396 KB |
Output is correct |
