oj.uz

Submission #1025383

# Submission time Handle Problem Language Result Execution time Memory
1025383 2024-07-17T01:16:20 Z vjudge1 Martian DNA (BOI18_dna) C++17
0 / 100
 336 ms 18516 KB 
#include <bits/stdc++.h>
#define ll long long
#define nikah ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll maxn = 2e5+7;
using namespace std;

ll n,k,r;
ll a[maxn];
map<ll,ll>m,m1,m2;

int main () {
	nikah
	cin>>n>>k>>r;
	for (ll i=1; i<=n; i++) {
		cin>>a[i];
		m1[a[i]]++; m2[a[i]]++;
	}
	bool cek = 0;
	for (ll i=1; i<=r; i++) {
		ll x,y; cin>>x>>y;
		m[x] = y;
		if (m1[x] < m[x]) {
			cek = 1;
		}
	}
	if (cek) {
		cout<<"impossible"<<endl;
	} else {
		ll l = 1, r = n;
		while (l <= r) {
			if (m1[a[l]] == m[a[l]]) {
				break;
			}
			m1[a[l]]--;
			l++;
		}
		while (l <= r) {
			if (m1[a[r]] == m[a[r]]) {
				break;
			}
			m1[a[r]]--;
			r--;
		}
		ll ans = r-l+1;
		l = 1, r = n;
		while (l <= r) {
			if (m2[a[r]] == m[a[r]]) {
				break;
			}
			m2[a[r]]--;
			r--;
		}
		while (l <= r) {
			if (m2[a[l]] == m[a[l]]) {
				break;
			}
			m2[a[l]]--;
			l++;
		}
		ans = min(ans, r - l + 1);
		cout<<ans<<endl;
	}
}

Subtask #1
0 / 16.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 32.0

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