Submission #1191048

#TimeUsernameProblemLanguageResultExecution timeMemory
1191048patgraGift Exchange (JOI24_ho_t4)C++20
50 / 100
2597 ms35316 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; int n, q, maxLog; vector<vector<pair<int, int>>> stMaxA, stMaxB; vector<int> a, b; pair<int, int> stQ(int l, int r, bool isA) { int k = 31 - __builtin_clz(r - l + 1); return isA ? max(stMaxA[l][k], stMaxA[r - (1 << k) + 1][k]) : max(stMaxB[l][k], stMaxB[r - (1 << k) + 1][k]); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; a.resize(n); b.resize(n); rep(i, 0, n) cin >> a[i]; rep(i, 0, n) cin >> b[i]; maxLog = 32 - __builtin_clz(n); stMaxA.resize(n, vector<pair<int, int>>(maxLog)); stMaxB.resize(n, vector<pair<int, int>>(maxLog)); rep(i, 0, n) stMaxA[i][0] = {a[i], i}, stMaxB[i][0] = {b[i], i}; rep(k, 1, maxLog) rep(i, 0, n) stMaxA[i][k] = max(stMaxA[i][k - 1], stMaxA[min(n - 1, i + (1 << (k - 1)))][k - 1]); rep(k, 1, maxLog) rep(i, 0, n) stMaxB[i][k] = max(stMaxB[i][k - 1], stMaxB[min(n - 1, i + (1 << (k - 1)))][k - 1]); cin >> q; rep(_, 0, q) { int l, r; cin >> l >> r; l--; r--; DC << l << ' ' << r << eol; vector<int> aa, bb; rep(i, l, r + 1) aa.pb(a[i]), bb.pb(b[i]); ranges::sort(aa), ranges::sort(bb); auto itA = 0; bool g = true, g2 = true; DC << ' '; repIn(i, aa) DC << i << ' '; DC << eol; DC << ' '; repIn(i, bb) DC << i << ' '; DC << eol; rep(i, 0, r - l + 1) { while(itA < r - l + 1 && aa[itA] < bb[i]) itA++; DC << ' ' << i << ' ' << itA << eol; if(itA > i) { g = false; break; } if(itA == i) { if(g2) { g2 = false; continue; } else { g = false; break; } } g2 = true; } cout << (g && g2 ? "Yes" : "No") << eol; } }
#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...