Submission #1025555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025555		kaysan	Martian DNA (BOI18_dna)	C++17	100 / 100	429 ms	42404 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,p;
ll a[maxn];
map<ll,ll>m,m1,m2;
set<ll>s;

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

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:30:16: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   30 |   if (s.size() == p) {
      |       ~~~~~~~~~^~~~
dna.cpp:19:7: warning: unused variable 'cek' [-Wunused-variable]
   19 |  bool cek = 0;
      |       ^~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32