oj.uz

Submission #522696

# Submission time Handle Problem Language Result Execution time Memory
522696 2022-02-05T12:42:48 Z bebecanvas Martian DNA (BOI18_dna) C++14
0 / 100
 25 ms 5012 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define endl '\n'

signed main(){
	
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k, r; cin >> n >> k >> r;
    int a[200005];
    for(int i=0; i<n; i++){cin >> a[i];}
	int b[200005]={0};
	int c[200005];
	for(int i=0; i<k; i++){c[i]=1;}
	for(int i=0; i<r; i++){
		int q, w; cin >> q >> w;
		c[q]= w;
	}
    
    int ans= -1;
    int count= 0;
    int s= 0; int e= 0;
    for(int i=0; i<n; i++){
		b[a[i]]++;
		if(b[a[i]]==c[a[i]]){count++;}
		if(count==k){e= i; ans= e-s+1; break;}
	}
    //cout << ans << endl;
    if(count==k){
		//cout << b[a[s]] << " " << c[a[s]] << endl;
		while(e!=n-1){
			//cout << e << endl;
			while(b[a[s]]>c[a[s]]){
				//cout << "lol" << endl;
				b[a[s]]--;
				s++;
				//cout << "s " << s << endl;
				ans= min(ans, e-s+1);
			}
			e++;
			b[a[e]]++;
			ans= min(ans, e-s+1);
		}
		cout << ans << endl;
	}else{
		cout << "impossible" << endl;
	}
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Incorrect 3 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Incorrect 3 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5012 KB Output is correct
2 Correct 12 ms 5000 KB Output is correct
3 Correct 13 ms 5004 KB Output is correct
4 Correct 13 ms 5000 KB Output is correct
5 Incorrect 17 ms 4940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 5004 KB Output isn't correct
2 Halted 0 ms 0 KB -