Submission #1174495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174495		beepbeepsheep	Martian DNA (BOI18_dna)	C++20	100 / 100	66 ms	24540 KiB

dna

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
#define ll long long
#define ii pair<ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=2e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll ptr[maxn];
ll arr[maxn];
vector<ll> adj[maxn];
vector<ll> nxt[maxn];
priority_queue<ii,vector<ii>,greater<ii>> pq;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n,m,k;
	cin>>n>>m>>k;
	for (int i=1;i<=n;i++){
		cin>>arr[i];
		adj[arr[i]].emplace_back(i);
	}
	for (int i=0;i<n;i++) adj[i].emplace_back(inf);
	ll a,b;
	ll stop=0;
	
	for (int i=1;i<=k;i++){
		cin>>a>>b;
		cerr<<a<<' '<<b<<endl;
		if (adj[a].size()<b){
			cout<<"impossible"<<endl;
			return 0;
		}
		ll sz=adj[a].size();
		cerr<<sz-b+1<<endl;
		for (int j=0;j<sz-b+1;j++){
			nxt[a].emplace_back(adj[a][j+b-1]); //end of interval
		}
		cerr<<nxt[a].back()<<endl;
		pq.emplace(adj[a][ptr[a]],a); //pos, char
		stop=max(stop,nxt[a][ptr[a]]);
	}
	ll ans=inf;
	for (int i=1;i<=n;i++){
		while (pq.size() && pq.top().first<i){
			tie(b,a)=pq.top();
			pq.pop();
			ptr[a]++;
			pq.emplace(adj[a][ptr[a]],a);
			stop=max(stop,nxt[a][ptr[a]]);
		}
		if (stop==inf) break;
		ans=min(ans,stop-i+1);
	}
	if (ans==inf) cout<<"impossible"<<endl;
	else cout<<ans<<endl;
	return 0;
}

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