Submission #1025383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025383		vjudge1	Martian DNA (BOI18_dna)	C++17	0 / 100	336 ms	18516 KiB

dna

#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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32