Submission #1127698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127698		nguyenphong233	Martian DNA (BOI18_dna)	C++20	100 / 100	80 ms	17736 KiB

dna

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)2e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n,k,r;
int req[MAX];
vector<int> adj[MAX];
int id[MAX],a[MAX];

signed main(){
	
	read();
	cin >> n >> k >> r;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		adj[a[i]].push_back(i);
		id[i] = (int)adj[a[i]].size() - 1;
	}
	for(int i = 1,b,q;i <= r;i++){
		cin >> b >> q;
		req[b] = q;
	}	
	
	set<int> st;
	int res = INF;
	
	for(int i = 1;i <= n;i++){
		if(req[a[i]] == 0)continue;
		if(id[i] > 0 && id[i] - 1 - req[a[i]] + 1 >= 0)
			st.erase(adj[a[i]][id[i] - req[a[i]]]);
		if(id[i] - req[a[i]] + 1 >= 0)
			st.insert(adj[a[i]][id[i] - req[a[i]] + 1]);
		
		//cout << i << " " << st.size() << '\n';
		if(st.size() == r)res = min(res,i - *st.begin() + 1);
	}
	
	if(res == INF)cout << "impossible\n";
	else cout << res << '\n';
	// cout << (res == INF ? "impossible" : res) << '\n';
	
	
	
}

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