제출 #1191053

#제출 시각아이디문제언어결과실행 시간메모리
1191053patgraGift Exchange (JOI24_ho_t4)C++20
10 / 100
118 ms48720 KiB
#include <bits/stdc++.h> #define rep(a,b,c) for(auto a = (b); a != (c); a++) #define repD(a,b,c) for(auto a = (b); a != (c); a--) #define repIn(a, b) for(auto a : (b)) #define repIn2(a, b, c) for(auto [a, b] : (c)) constexpr bool dbg = 0; #define DEBUG if constexpr(dbg) #define DC DEBUG std::cerr #define eol std::endl #define ll long long #define pb push_back using namespace std; constexpr int maxn = 5e5 + 7, tb = 1 << 20, maxq = 2e5 + 7; int n, q; int a[maxn], b[maxn], lastLeft[maxn], firstRight[maxn]; int tr[2 * tb], lz[2 * tb]; pair<int, int> queries[maxq]; vector<int> queriesAt[maxn], offAt[maxn]; int answers[maxq]; int tMax(int l, int r) { l += tb, r += tb; auto ans = max(tr[l], tr[r]); while(l / 2 != r / 2) { if(l % 2 == 0) ans = max(ans, tr[l + 1]); if(r % 2 == 1) ans = max(ans, tr[r - 1]); l /= 2; r /= 2; ans = max(ans, max(lz[l], lz[r])); } while(l > 1) l /= 2, ans = max(ans, lz[l]); return ans; } void tSetMax(int l, int r, int x) { l += tb; r += tb; tr[l] = tr[r] = x; while(l / 2 != r / 2) { if(l % 2 == 0) tr[l + 1] = lz[l + 1] = x; if(r % 2 == 1) tr[r - 1] = lz[r - 1] = x; l /= 2; r /= 2; tr[l] = max(max(tr[2 * l], tr[2 * l + 1]), lz[l]); tr[r] = max(max(tr[2 * r], tr[2 * r + 1]), lz[r]); } while(l / 2) l /= 2, tr[l] = max(max(tr[2 * l], tr[2 * l + 1]), lz[l]); } int tMin(int l, int r) { l += tb, r += tb; auto ans = min(tr[l], tr[r]); while(l / 2 != r / 2) { if(l % 2 == 0) ans = min(ans, tr[l + 1]); if(r % 2 == 1) ans = min(ans, tr[r - 1]); l /= 2; r /= 2; ans = min(ans, min(lz[l], lz[r])); } while(l > 1) l /= 2, ans = min(ans, lz[l]); return ans; } void tSetMin(int l, int r, int x) { l += tb; r += tb; tr[l] = tr[r] = x; while(l / 2 != r / 2) { if(l % 2 == 0) tr[l + 1] = lz[l + 1] = x; if(r % 2 == 1) tr[r - 1] = lz[r - 1] = x; l /= 2; r /= 2; tr[l] = min(min(tr[2 * l], tr[2 * l + 1]), lz[l]); tr[r] = min(min(tr[2 * r], tr[2 * r + 1]), lz[r]); } while(l / 2) l /= 2, tr[l] = min(min(tr[2 * l], tr[2 * l + 1]), lz[l]); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; rep(i, 0, n) cin >> a[i]; rep(i, 0, n) cin >> b[i]; rep(i, 0, 2 * tb) tr[i] = lz[i] = -1; rep(i, 0, n) { lastLeft[i] = tMax(b[i], a[i]); DC << "ll[" << i << "] = " << lastLeft[i] << eol; tSetMax(b[i], a[i], i); } rep(i, 0, 2 * tb) tr[i] = lz[i] = n; repD(i, n - 1, -1) { firstRight[i] = tMin(b[i], a[i]); DC << "fr[" << i << "] = " << firstRight[i] << eol; tSetMin(b[i], a[i], i); } cin >> q; rep(i, 0, q) { int l, r; cin >> l >> r; l--; r--; queries[i] = {l, r}; queriesAt[r].pb(i); } rep(i, 0, 2 * tb) tr[i] = lz[i] = n; rep(i, 0, n) tr[i + tb] = lz[i + tb] = lastLeft[i]; repD(i, tb - 1, 0) tr[i] = max(tr[2 * i], tr[2 * i + 1]); rep(i, 0, n) if(firstRight[i] != n) offAt[firstRight[i]].pb(i); rep(i, 0, n) { repIn(j, offAt[i]) tSetMin(j, j, j); repIn(j, queriesAt[i]) answers[j] = tMin(queries[j].first, queries[j].second) >= queries[j].first; } rep(i, 0, q) cout << (answers[i] ? "Yes\n" : "No\n"); }
#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...