Submission #631584

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
631584	2022-08-18 09:23:55	bachhoangxuan	Martian DNA (BOI18_dna)	C++17	100 / 100	61 ms	4564 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;
#define maxn 200005
int num[maxn],n,k,q,cnt[maxn],a[maxn];
bool check(int mid){
    int x=0;
    for(int i=0;i<k;i++) cnt[i]=0;
    for(int i=1;i<=mid;i++){
        cnt[a[i]]++;
        if(cnt[a[i]]==num[a[i]]) x++;
    }
    if(x==q) return true;
    for(int i=mid+1;i<=n;i++){
        cnt[a[i]]++;
        if(cnt[a[i]]==num[a[i]]) x++;
        if(cnt[a[i-mid]]==num[a[i-mid]]) x--;
        cnt[a[i-mid]]--;
        if(x==q) return true;
    }
    return false;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> k >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=q;i++){
        int x,c;cin >> x >> c;
        num[x]=c;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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