Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Forget the interactive wrapper for hacks. You are given the actual permutation, so the query limit is just lore. The job is: among the listed intervals, find the largest MEX.
For a fixed value , an interval has MEX at least iff it contains every value . Since is a permutation, that means it must contain all their positions.
Let be the position of value . Define
Then some given range has MEX at least iff some given range fully contains .
Build best[x] = max r among all given ranges with left endpoint . Then is contained in some listed range exactly when best[L_k] >= R_k.
Scan while updating from pos[k-1]. The largest with best[L_k] >= R_k is the answer. MEX works only when some given interval contains all positions, i.e. the whole array.
We are in the hacked version, so the “interactive” part is decorative confetti. We get the whole permutation and all ranges directly.
Because is a permutation, every value appears exactly once. Let
An interval has MEX at least iff it contains all values
So it must contain all positions . Define:
Then some given range has MEX at least iff some given range contains .
A range contains exactly when and . Preprocess:
mx[l] = maximum right endpoint among ranges starting exactly at l;best[x] = max(mx[1], mx[2], ..., mx[x]).Now some listed range contains iff:
best[L] >= RThat gives each check in .
Now scan . When adding value , update:
If best[L] >= R, then some listed interval has MEX at least $k`, so update the answer.
This checks every possible MEX threshold. If a range also contains value , then its MEX is even bigger, which is fine. We’re maximizing, not trying to be weirdly precise for no reason.
Correctness
For any , an interval has MEX at least iff it contains every value from to . Since each value appears once, this is equivalent to containing every position , which is equivalent to containing .
The preprocessing makes best[L] the farthest right endpoint among all ranges with left endpoint at most . Therefore best[L_k] >= R_k is true exactly when some listed range contains .
The scan maintains the exact for each , so it tests exactly whether MEX at least is achievable. The largest achievable is exactly the maximum MEX over all given ranges.
Complexity
Each test case runs in
with memory.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, q;
cin >> n >> q;
vector<int> pos(n);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
pos[x] = i;
}
vector<int> best(n + 1, 0);
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
best[l] = max(best[l], r);
}
for (int i = 1; i <= n; i++) {
best[i] = max(best[i], best[i - 1]);
}
int ans = 0;
int L = n + 1, R = 0;
for (int k = 1; k <= n; k++) {
int at = pos[k - 1];
L = min(L, at);
R = max(R, at);
if (best[L] >= R) ans = k;
}
cout << ans << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, q;
cin >> n >> q;
vector<int> pos(n);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
pos[x] = i;
}
vector<int> best(n + 1, 0);
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
best[l] = max(best[l], r);
}
for (int i = 1; i <= n; i++) {
best[i] = max(best[i], best[i - 1]);
}
int ans = 0;
int L = n + 1, R = 0;
for (int k = 1; k <= n; k++) {
int at = pos[k - 1];
L = min(L, at);
R = max(R, at);
if (best[L] >= R) ans = k;
}
cout << ans << '\n';
}
}