This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
#define N 500015
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, q, L1[N], R1[N], L2[N], R2[N], L[N], R[N], ord[2 * N], ans[N];
pii arr[N];
vector<int> qry[2 * N], rem[N];
vector<pii> query[N];
void solve(int l, int r){
int mid = (l + r) >> 1;
set<int> A;
for (int i = l; i <= mid; i++)
if (ord[i] > n && arr[ord[i] - n].x - 1 > mid)
qry[min(r, arr[ord[i] - n].x - 1)].emplace_back(ord[i] - n);
for (int i = mid + 1; i <= r; i++){ // B match A
if (ord[i] <= n)
A.insert(ord[i]);
for (auto j : qry[i]){
if (A.empty())
continue;
auto it = A.upper_bound(j);
if (it != A.end())
R1[j] = min(R1[j], *it);
if (it != A.begin())
L1[j] = max(L1[j], *prev(it));
}
qry[i].clear();
}
}
void merge(int l, int r){
if (l == r)
return;
int mid = (l + r) >> 1;
merge(l, mid), merge(mid + 1, r);
solve(l, r);
}
struct segtree{
int seg[N];
void modify(int l, int r, int i, int p, int c){
if (l == r){
seg[i] = c;
return;
}
int mid = (l + r) >> 1;
if (p <= mid) modify(l, mid, i << 1, p, c);
else modify(mid + 1, r, i << 1 | 1, p, c);
seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
}
int query(int l, int r, int i, int ll, int rr){
if (ll <= l && rr >= r)
return seg[i];
int mid = (l + r) >> 1;
if (rr <= mid) return query(l, mid, i << 1, ll, rr);
else if (ll > mid) return query(mid + 1, r, i << 1 | 1, ll, rr);
else return min(query(l, mid, i << 1, ll, rr), query(mid + 1, r, i << 1 | 1, ll, rr));
}
}seg;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i].x, ord[arr[i].x] = i;
for (int i = 1; i <= n; i++)
cin >> arr[i].y, ord[arr[i].y] = i + n;
fill(R1, R1 + N, n + 1);
fill(R2, R2 + N, n + 1);
merge(1, 2 * n);
set<int> B;
for (int i = 1; i <= 2 * n; i++){
if (ord[i] <= n){
B.erase(ord[i]);
auto it = B.upper_bound(ord[i]);
if (it != B.end())
R2[ord[i]] = min(R2[ord[i]], *it);
if (it != B.begin())
L2[ord[i]] = max(L2[ord[i]], *prev(it));
}
else B.insert(ord[i] - n);
}
cin >> q;
for (int i = 1; i <= q; i++){
int l, r; cin >> l >> r;
query[r].emplace_back(l, i);
}
for (int i = 1; i <= n; i++){
L[i] = max(L1[i], L2[i]);
R[i] = min(R1[i], R2[i]);
rem[R[i]].emplace_back(i);
}
for (int i = 1; i <= n; i++){
seg.modify(1, n, 1, i, L[i]);
for (auto id : rem[i])
seg.modify(1, n, 1, id, n + 1);
for (auto [l, id] : query[i])
ans[id] = (seg.query(1, n, 1, l, i) >= l) ? 1 : 0;
}
for (int i = 1; i <= q; i++)
cout << ((ans[i] == 1) ? "Yes\n" : "No\n");
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |