제출 #996299

#제출 시각아이디문제언어결과실행 시간메모리
996299MilosMilutinovicGift Exchange (JOI24_ho_t4)C++14
50 / 100
2545 ms14532 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> b(n); for (int i = 0; i < n; i++) { cin >> b[i]; } vector<int> prv(n); { vector<int> mx(16 * n, -1); vector<int> tag(16 * n, -1); auto Push = [&](int x) { mx[x * 2] = max(mx[x * 2], tag[x]); mx[x * 2 + 1] = max(mx[x * 2 + 1], tag[x]); tag[x * 2] = max(tag[x * 2], tag[x]); tag[x * 2 + 1] = max(tag[x * 2 + 1], tag[x]); tag[x] = -1; }; function<void(int, int, int, int, int, int)> Modify = [&](int x, int l, int r, int ll, int rr, int v) { if (ll <= l && r <= rr) { mx[x] = max(mx[x], v); tag[x] = max(tag[x], v); Push(x); return; } Push(x); int mid = (l + r) >> 1; if (rr <= mid) { Modify(x * 2, l, mid, ll, rr, v); } else if (ll > mid) { Modify(x * 2 + 1, mid + 1, r, ll, rr, v); } else { Modify(x * 2, l, mid, ll, rr, v); Modify(x * 2 + 1, mid + 1, r, ll, rr, v); } mx[x] = max(mx[x * 2], mx[x * 2 + 1]); }; function<int(int, int, int, int, int)> Query = [&](int x, int l, int r, int ll, int rr) { if (ll <= l && r <= rr) { return mx[x]; } Push(x); int mid = (l + r) >> 1; int ret = 0; if (rr <= mid) { ret = Query(x * 2, l, mid, ll, rr); } else if (ll > mid) { ret = Query(x * 2 + 1, mid + 1, r, ll, rr); } else { ret = max(Query(x * 2, l, mid, ll, rr), Query(x * 2 + 1, mid + 1, r, ll, rr)); } mx[x] = max(mx[x * 2], mx[x * 2 + 1]); return ret; }; for (int i = 0; i < n; i++) { prv[i] = Query(1, 1, 2 * n, b[i], a[i]); Modify(1, 1, 2 * n, b[i], a[i], i); } } vector<int> nxt(n); { vector<int> mn(16 * n, n); vector<int> tag(16 * n, n); auto Push = [&](int x) { mn[x * 2] = min(mn[x * 2], tag[x]); mn[x * 2 + 1] = min(mn[x * 2 + 1], tag[x]); tag[x * 2] = min(tag[x * 2], tag[x]); tag[x * 2 + 1] = min(tag[x * 2 + 1], tag[x]); tag[x] = n; }; function<void(int, int, int, int, int, int)> Modify = [&](int x, int l, int r, int ll, int rr, int v) { if (ll <= l && r <= rr) { mn[x] = min(mn[x], v); tag[x] = min(tag[x], v); Push(x); return; } Push(x); int mid = (l + r) >> 1; if (rr <= mid) { Modify(x * 2, l, mid, ll, rr, v); } else if (ll > mid) { Modify(x * 2 + 1, mid + 1, r, ll, rr, v); } else { Modify(x * 2, l, mid, ll, rr, v); Modify(x * 2 + 1, mid + 1, r, ll, rr, v); } mn[x] = min(mn[x * 2], mn[x * 2 + 1]); }; function<int(int, int, int, int, int)> Query = [&](int x, int l, int r, int ll, int rr) { if (ll <= l && r <= rr) { return mn[x]; } Push(x); int mid = (l + r) >> 1; int ret = 0; if (rr <= mid) { ret = Query(x * 2, l, mid, ll, rr); } else if (ll > mid) { ret = Query(x * 2 + 1, mid + 1, r, ll, rr); } else { ret = min(Query(x * 2, l, mid, ll, rr), Query(x * 2 + 1, mid + 1, r, ll, rr)); } mn[x] = min(mn[x * 2], mn[x * 2 + 1]); return ret; }; for (int i = n - 1; i >= 0; i--) { nxt[i] = Query(1, 1, 2 * n, b[i], a[i]); Modify(1, 1, 2 * n, b[i], a[i], i); } } int q; cin >> q; while (q--) { int l, r; cin >> l >> r; --l; --r; bool ok = true; for (int i = l; i <= r; i++) { if (prv[i] < l && r < nxt[i]) { ok = false; } } cout << (ok ? "Yes" : "No") << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...