oj.uz

Submission #731666

# Submission time Handle Problem Language Result Execution time Memory
731666 2023-04-27T18:15:25 Z NintsiChkhaidze Martian DNA (BOI18_dna) C++17
0 / 100
 28 ms 1684 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5,inf=1e9;
int a[N],mn[N],cnt[N];
 
signed main (){
	
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,k,R;
	cin>>n>>k>>R;
	
	for (int i = 1; i <= n; i++){
		cin>>a[i];
	}
	
	for (int i = 1; i <= k; i++) mn[i] = inf;
	for (int i = 1; i <= R; i++){
		int x,y;
		cin>>x>>y;
		mn[x] = y;
	}
	
	int C = R,r = 1,ans=inf;
	cnt[a[1]]++;
	if (cnt[a[1]] >= mn[a[1]]) --C;
	
	for (int i = 1; i <= n; i++){
		while (C > 0 && r + 1 <= n){
			++r;
			cnt[a[r]]++;
			if (cnt[a[r]] - 1 < mn[a[r]] && cnt[a[r]] >= mn[a[r]]) 
				C--;
		}
		if (C == 0) ans=min(ans,r - i + 1);
		
		cnt[a[i]]--;
		if (cnt[a[i]] + 1 == mn[a[r]] && cnt[a[i]] < mn[a[r]]) ++C;
	}
	if(ans==inf) cout<<"impossible";
	else cout<<ans;
}

Subtask #1
0 / 16.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 32.0

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