제출 #1095300

#제출 시각아이디문제언어결과실행 시간메모리
1095300TriseedotGift Exchange (JOI24_ho_t4)C++17
50 / 100
2539 ms13180 KiB
// In honor of El Psy Congroo //#define _GLIBCXX_DEBUG #include <bits/stdc++.h> #include <random> #include <chrono> using namespace std; // variables using ld = long double; using ll = long long; using ull = unsigned long long; template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; // bitwise operations #define cnt_bit(n) __builtin_popcountll(n) #define low_bit(n) ((n) & (-(n))) #define bit(n, i) (((n) >> (i)) & 1) #define set_bit(n, i) ((n) | (1ll << (i))) #define reset_bit(n, i) ((n) & ~(1ll << (i))) #define flip_bit(n, i) ((n) ^ (1ll << (i))) // math #define sqr(n) ((n) * (n)) int log2_floor(ull n) { return n ? __builtin_clzll(1) - __builtin_clzll(n) : -1; } // vector #define len(x) (int) x.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() template <typename T> istream& operator>>(istream& is, vector<T>& v) { for(auto& el : v) { is >> el; } return is; } template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { for (int i = 0; i < len(v); i++) { if (i) os << ' '; os << v[i]; } return os; } template<class... Args> auto create(size_t n, Args&&... args) { if constexpr(sizeof...(args) == 1) { return vector(n, args...); } else { return vector(n, create(args...)); } } template<typename T> void remove_dups(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } // random mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); //////solution start////// struct DSU { int n; vector<int> p; void build(int N) { n = N; p.resize(n); iota(p.begin(), p.end(), 0); } int get(int i) { if (p[i] == i) return i; return p[i] = get(p[i]); } bool unite(int i, int j) { i = get(i); j = get(j); if (i == j) return false; p[i] = j; return true; } }; void solve() { int n; cin >> n; vector<int> a(n), b(n); cin >> a >> b; for (int i = 0; i < n; i++) { a[i]--, b[i]--; } int m; cin >> m; vector<pair<int, int>> q(m); for (int i = 0; i < m; i++) { cin >> q[i].first >> q[i].second; q[i].first--, q[i].second--; } vector<optional<int>> l(n), r(n); set<pair<int, int>> curr; for (int i = 0; i < n; i++) { while (true) { auto it = curr.lower_bound({b[i], -1}); if (it == curr.end() || it->first > a[i]) break; int j = it->second; if (!r[j].has_value() || r[j] > i) r[j] = i; if (!l[i].has_value() || l[i] < j) l[i] = j; curr.erase(it); } curr.insert({a[i], i}); } curr.clear(); for (int i = n - 1; i >= 0; i--) { while (true) { auto it = curr.lower_bound({b[i], -1}); if (it == curr.end() || it->first > a[i]) break; int j = it->second; if (!r[i].has_value() || r[i] > j) r[i] = j; if (!l[j].has_value() || l[j] < i) l[j] = i; curr.erase(it); } curr.insert({a[i], i}); } for (auto [i, j] : q) { [&] () { for (int k = i; k <= j; k++) { if ((!l[k].has_value() || l[k] < i) && (!r[k].has_value() || r[k] > j)) { cout << "No\n"; return; } } cout << "Yes\n"; } (); } } //////solution end////// signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; for (int i = 1; i <= tt; i++) { solve(); } }
#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...