Submission #895978

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
895978	2023-12-31T09:57:53 Z	pcc	Martian DNA (BOI18_dna)	C++14	68 / 100	34 ms	4668 KB

dna

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 2e5+10;
int cnt[mxn];
int N,K,Q;
int arr[mxn];
int good = 0;
int lim[mxn];

inline void add(int k){
	cnt[k]++;
	if(cnt[k] == lim[k])good++;
	return;
}
inline void del(int k){
	if(cnt[k] == lim[k])good--;
	cnt[k]--;
	return;
}

inline bool check(int len){
	memset(cnt,0,sizeof(cnt));
	good = 0;
	for(int i = 0;i<K;i++){
		if(!lim[i])good++;
	}
	for(int i = 1;i<len;i++){
		add(arr[i]);
	}
	for(int i = len;i<=N;i++){
		add(arr[i]);
		if(good == K)return true;
		del(arr[i-len+1]);
	}
	return false;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	while(Q--){
		int a,b;
		cin>>a>>b;
		lim[a] = b;
	}
	int l = 0,r = N;
	while(l != r){
		int mid = (l+r)>>1;
		if(check(mid))r = mid;
		else l = mid+1;
	}
	if(check(l))cout<<l;
	else cout<<"impossible";
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 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	2516 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	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 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	2396 KB	Output is correct
3	Correct	2 ms	2652 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	2 ms	2652 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
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2392 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	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2908 KB	Output is correct
2	Correct	19 ms	2904 KB	Output is correct
3	Correct	10 ms	2948 KB	Output is correct
4	Correct	14 ms	2908 KB	Output is correct
5	Correct	18 ms	3676 KB	Output is correct
6	Correct	13 ms	2908 KB	Output is correct
7	Correct	13 ms	3164 KB	Output is correct
8	Correct	24 ms	3656 KB	Output is correct
9	Correct	15 ms	3420 KB	Output is correct
10	Correct	13 ms	2908 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	2652 KB	Output is correct
14	Correct	1 ms	2652 KB	Output is correct
15	Correct	1 ms	2652 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	1 ms	2396 KB	Output is correct
21	Correct	1 ms	2396 KB	Output is correct
22	Correct	1 ms	2508 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

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	4668 KB	Output is correct
2	Correct	27 ms	4184 KB	Output is correct
3	Correct	34 ms	3928 KB	Output is correct
4	Incorrect	9 ms	2908 KB	Output isn't correct
5	Halted	0 ms	0 KB	-