Submission #452064

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
452064	2021-08-03 17:28:20	soba	Martian DNA (BOI18_dna)	C++14	100 / 100	955 ms	8344 KiB

dna

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N = 2e5+3;
set<int>s;
int reqs[N] , arr[N] , cnt[N] , tmp[N];
int n , k , q , a , b;
bool check(int x)
{
    s.clear();
    memset(tmp , 0 , sizeof tmp);
    int r = x;
    for(int i = 0 ; i < x ; i++)
    {
        tmp[arr[i]]++;
    }
    for(int i = 0 ; i < k ; i++)
    {
        if(reqs[i]>tmp[i])
            s.insert(i);
    }
    if(s.empty())
        return true;
    set<int>::iterator it;
    while(r<n)
    {
        tmp[arr[r]]++;
        tmp[arr[r-x]]--;
        if(tmp[arr[r]]>=reqs[arr[r]] && s.find(arr[r])!=s.end())
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32