Submission #378258

#	Time	Username	Problem	Language	Result	Execution time	Memory
378258		Nima_Naderi	Martian DNA (BOI18_dna)	C++14	100 / 100	659 ms	36064 KiB

dna

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

//typedef long long ll;
typedef int ll;
const ll MXN = 2e5 + 10;
const ll LOG = 19;
ll n, k, q, ans, ml, mr, ts;
ll A[MXN], T[MXN], B[MXN], Id[MXN], Fen[MXN], come[MXN];
ll rem[MXN], Idq[MXN], low[MXN], hig[MXN], ith[MXN];
vector<pair<ll, ll>> Q, Qry[MXN];
vector<ll> Pos[MXN];
bool ANS[MXN];
void Upd(ll p, ll x){
	for(; p < MXN; p += p & -p) Fen[p] += x;
}
void Upd(ll l, ll r, ll x){
	Upd(l, +x), Upd(r + 1, -x);
}
ll Get(ll p){
	ll s = 0;
	for(; p; p -= p & -p) s += Fen[p];
	return s;
}
void Solve(){
	memset(Fen, 0, sizeof Fen), memset(ANS, 0, sizeof ANS);
	for(int i = 0; i < ts; i ++){
		ll l, r; tie(l, r) = Q[i];
		Qry[r].push_back({l, i});
	}
	for(int i = 1; i <= q; i ++){
		Upd(1, Pos[B[i]][come[B[i]] - T[i]], +1);
	}
	for(auto Pr : Qry[mr]){
		ll j, id; tie(j, id) = Pr;
		ANS[id] = (Get(j) == q);
	}
	for(int i = mr + 1; i <= n; i ++){
		if(Idq[A[i]]){
			ll ted = T[Idq[A[i]]], th = ith[i]; 
			Upd(Pos[A[i]][th - ted] + 1, Pos[A[i]][th - ted + 1], 1);
		}
		for(auto Pr : Qry[i]){
			ll j, id; tie(j, id) = Pr;
			ANS[id] = (Get(j) == q);
		}
	}
	for(int i = 0; i < ts; i ++){
		Qry[Q[i].second].clear();
	}
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> k >> q;
	for(int i = 1; i <= n; i ++){
		cin >> A[i], A[i] ++;
		Pos[A[i]].push_back(i);
		ith[i] = rem[A[i]], rem[A[i]] ++;
	}
	for(int i = 1; i <= q; i ++) cin >> B[i] >> T[i], B[i] ++, Idq[B[i]] = i;
	for(int j = 1; j <= q; j ++){
		if(rem[B[j]] < T[j]){
			return cout << "impossible\n", 0;
		}
	}
	ans = n, mr = 1;
	for(int i = 1; i <= q; i ++){
		mr = max(mr, Pos[B[i]][T[i] - 1]);
	}
	for(int i = 1; i <= mr; i ++) come[A[i]] ++;
	for(int l = 1; l <= n; l ++){
		ml = l;
		rem[A[l]] --;
		if(Idq[A[l]] && rem[A[l]] < T[Idq[A[l]]]) break;
	}
	for(int l = 1; l <= ml; l ++){
		low[l] = l - 1, hig[l] = n;
	}
	for(int lg = 0; lg < LOG; lg ++){
		Q.clear(), ts = 0;
		for(int l = 1; l <= ml; l ++){
			if(hig[l] - low[l] > 1){
				ll mid = (low[l] + hig[l]) / 2;
				Id[l] = ts ++;
				Q.push_back({l, mid});
			}
		}
		Solve();
		for(int l = 1; l <= ml; l ++){
			if(hig[l] - low[l] > 1){
				ll mid = (low[l] + hig[l]) / 2;
				if(ANS[Id[l]]) hig[l] = mid;
				else low[l] = mid;
			}
		}
	}
	for(int l = 1; l <= ml; l ++){
		ans = min(ans, hig[l] - l + 1);
	}
	cout << ans << '\n';
	return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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