Submission #895980

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
895980	2023-12-31T10:01:16 Z	pcc	Martian DNA (BOI18_dna)	C++14	68 / 100	37 ms	9820 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>
#define int ll

const int mxn = 4e5+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;
}

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";
}

Compilation message

dna.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7516 KB	Output is correct
2	Correct	2 ms	7516 KB	Output is correct
3	Correct	2 ms	7516 KB	Output is correct
4	Correct	2 ms	7516 KB	Output is correct
5	Correct	2 ms	7516 KB	Output is correct
6	Correct	2 ms	7668 KB	Output is correct
7	Correct	2 ms	7524 KB	Output is correct
8	Correct	2 ms	7512 KB	Output is correct
9	Correct	2 ms	7516 KB	Output is correct

Subtask #2

24.0 / 24.0

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

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	7516 KB	Output is correct
2	Correct	19 ms	7624 KB	Output is correct
3	Correct	11 ms	7516 KB	Output is correct
4	Correct	13 ms	7516 KB	Output is correct
5	Correct	20 ms	9692 KB	Output is correct
6	Correct	14 ms	7620 KB	Output is correct
7	Correct	14 ms	7516 KB	Output is correct
8	Correct	27 ms	9432 KB	Output is correct
9	Correct	18 ms	7640 KB	Output is correct
10	Correct	14 ms	7516 KB	Output is correct
11	Correct	2 ms	7516 KB	Output is correct
12	Correct	3 ms	7516 KB	Output is correct
13	Correct	2 ms	7516 KB	Output is correct
14	Correct	2 ms	7516 KB	Output is correct
15	Correct	2 ms	7516 KB	Output is correct
16	Correct	2 ms	7516 KB	Output is correct
17	Correct	2 ms	7516 KB	Output is correct
18	Correct	2 ms	7516 KB	Output is correct
19	Correct	2 ms	7516 KB	Output is correct
20	Correct	2 ms	7516 KB	Output is correct
21	Correct	2 ms	7516 KB	Output is correct
22	Correct	2 ms	7516 KB	Output is correct
23	Correct	2 ms	7516 KB	Output is correct
24	Correct	2 ms	7620 KB	Output is correct
25	Correct	2 ms	7516 KB	Output is correct

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	9820 KB	Output is correct
2	Correct	29 ms	9820 KB	Output is correct
3	Correct	37 ms	9820 KB	Output is correct
4	Incorrect	10 ms	7512 KB	Output isn't correct
5	Halted	0 ms	0 KB	-