oj.uz

Submission #330265

# Submission time Handle Problem Language Result Execution time Memory
330265 2020-11-24T10:30:05 Z nandonathaniel Martian DNA (BOI18_dna) C++14
68 / 100
 2000 ms 13036 KB 
#include<bits/stdc++.h>
using namespace std;

int mini[200005],byk[200005];
int s[200005];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n,k,r,x,y;
    cin >> n >> k >> r;
    for(int i=1;i<=n;i++)cin >> s[i];
    for(int i=1;i<=r;i++){
    	cin >> x >> y;
    	mini[x]=y;
	}
	int ki=1,ka=n,ans=n+1;
	while(ki<=ka){
		int mid=(ki+ka)/2;
		set<int> valid;
		for(int i=0;i<k;i++){
			if(mini[i]==0)valid.insert(i);
			byk[i]=0;
		}
		for(int i=1;i<=mid;i++){
			byk[s[i]]++;
			if(byk[s[i]]==mini[s[i]])valid.insert(s[i]);
		}
		if(valid.size()==k){
			ans=mid;
			ka=mid-1;
			continue;
		}
		bool ada=false;
		for(int i=mid+1;i<=n;i++){
			byk[s[i-mid]]--;
			if(byk[s[i-mid]]==mini[s[i-mid]]-1)valid.erase(s[i-mid]);
			byk[s[i]]++;
			if(byk[s[i]]==mini[s[i]])valid.insert(s[i]);
			if(valid.size()==k){
				ada=true;
				break;
			}
		}
		if(ada){
			ans=mid;
			ka=mid-1;
		}
		else ki=mid+1;
	}
	if(ans==n+1)cout << "impossible\n";
	else cout << ans << '\n';
	return 0;
}

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:28:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   if(valid.size()==k){
      |      ~~~~~~~~~~~~^~~
dna.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |    if(valid.size()==k){
      |       ~~~~~~~~~~~~^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1588 KB Output is correct
2 Correct 36 ms 1516 KB Output is correct
3 Correct 22 ms 1516 KB Output is correct
4 Correct 32 ms 1516 KB Output is correct
5 Correct 277 ms 6380 KB Output is correct
6 Correct 31 ms 1516 KB Output is correct
7 Correct 30 ms 1644 KB Output is correct
8 Correct 664 ms 12660 KB Output is correct
9 Correct 51 ms 2700 KB Output is correct
10 Correct 40 ms 1644 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 4 ms 492 KB Output is correct
14 Correct 6 ms 620 KB Output is correct
15 Correct 4 ms 492 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 0 ms 364 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1557 ms 7404 KB Output is correct
2 Correct 1435 ms 6088 KB Output is correct
3 Correct 537 ms 5868 KB Output is correct
4 Correct 16 ms 1516 KB Output is correct
5 Correct 114 ms 4972 KB Output is correct
6 Execution timed out 2090 ms 13036 KB Time limit exceeded
7 Halted 0 ms 0 KB -