Submission #378258

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378258	2021-03-16T10:52:34 Z	Nima_Naderi	Martian DNA (BOI18_dna)	C++14	100 / 100	659 ms	36064 KB

///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.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	10732 KB	Output is correct
2	Correct	8 ms	10860 KB	Output is correct
3	Correct	8 ms	10732 KB	Output is correct
4	Correct	7 ms	9836 KB	Output is correct
5	Correct	7 ms	9836 KB	Output is correct
6	Correct	8 ms	10732 KB	Output is correct
7	Correct	8 ms	10732 KB	Output is correct
8	Correct	8 ms	10860 KB	Output is correct
9	Correct	9 ms	10732 KB	Output is correct

Subtask #2
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	10988 KB	Output is correct
2	Correct	11 ms	10988 KB	Output is correct
3	Correct	10 ms	11116 KB	Output is correct
4	Correct	12 ms	11244 KB	Output is correct
5	Correct	10 ms	11116 KB	Output is correct
6	Correct	17 ms	11116 KB	Output is correct
7	Correct	8 ms	10732 KB	Output is correct
8	Correct	8 ms	10732 KB	Output is correct
9	Correct	8 ms	10732 KB	Output is correct
10	Correct	7 ms	9856 KB	Output is correct
11	Correct	7 ms	9836 KB	Output is correct
12	Correct	8 ms	10732 KB	Output is correct
13	Correct	8 ms	10732 KB	Output is correct
14	Correct	8 ms	10732 KB	Output is correct
15	Correct	8 ms	10732 KB	Output is correct

Subtask #3
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	209 ms	21576 KB	Output is correct
2	Correct	276 ms	22688 KB	Output is correct
3	Correct	348 ms	23900 KB	Output is correct
4	Correct	267 ms	22836 KB	Output is correct
5	Correct	150 ms	31528 KB	Output is correct
6	Correct	27 ms	13916 KB	Output is correct
7	Correct	25 ms	12908 KB	Output is correct
8	Correct	162 ms	35132 KB	Output is correct
9	Correct	143 ms	28512 KB	Output is correct
10	Correct	275 ms	24260 KB	Output is correct
11	Correct	13 ms	10988 KB	Output is correct
12	Correct	11 ms	10988 KB	Output is correct
13	Correct	10 ms	11116 KB	Output is correct
14	Correct	10 ms	11244 KB	Output is correct
15	Correct	10 ms	11116 KB	Output is correct
16	Correct	15 ms	11116 KB	Output is correct
17	Correct	8 ms	10732 KB	Output is correct
18	Correct	8 ms	10732 KB	Output is correct
19	Correct	9 ms	10860 KB	Output is correct
20	Correct	7 ms	9836 KB	Output is correct
21	Correct	7 ms	9836 KB	Output is correct
22	Correct	8 ms	10732 KB	Output is correct
23	Correct	8 ms	10732 KB	Output is correct
24	Correct	8 ms	10732 KB	Output is correct
25	Correct	8 ms	10732 KB	Output is correct

Subtask #4
32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	659 ms	27368 KB	Output is correct
2	Correct	502 ms	26188 KB	Output is correct
3	Correct	336 ms	26144 KB	Output is correct
4	Correct	328 ms	23680 KB	Output is correct
5	Correct	71 ms	18028 KB	Output is correct
6	Correct	547 ms	36064 KB	Output is correct
7	Correct	111 ms	15724 KB	Output is correct
8	Correct	202 ms	25288 KB	Output is correct
9	Correct	205 ms	21604 KB	Output is correct
10	Correct	267 ms	22688 KB	Output is correct
11	Correct	361 ms	23896 KB	Output is correct
12	Correct	265 ms	22836 KB	Output is correct
13	Correct	154 ms	31652 KB	Output is correct
14	Correct	26 ms	13932 KB	Output is correct
15	Correct	25 ms	12908 KB	Output is correct
16	Correct	158 ms	35040 KB	Output is correct
17	Correct	142 ms	28512 KB	Output is correct
18	Correct	275 ms	24132 KB	Output is correct
19	Correct	13 ms	10988 KB	Output is correct
20	Correct	11 ms	10988 KB	Output is correct
21	Correct	10 ms	11116 KB	Output is correct
22	Correct	10 ms	11244 KB	Output is correct
23	Correct	9 ms	11116 KB	Output is correct
24	Correct	14 ms	11116 KB	Output is correct
25	Correct	9 ms	10876 KB	Output is correct
26	Correct	8 ms	10732 KB	Output is correct
27	Correct	9 ms	10732 KB	Output is correct
28	Correct	7 ms	9836 KB	Output is correct
29	Correct	7 ms	9836 KB	Output is correct
30	Correct	8 ms	10732 KB	Output is correct
31	Correct	8 ms	10732 KB	Output is correct
32	Correct	8 ms	10732 KB	Output is correct
33	Correct	8 ms	10732 KB	Output is correct

Submission #378258

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 28.0 / 28.0

Subtask #4 32.0 / 32.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
28.0 / 28.0

Subtask #4
32.0 / 32.0