Submission #873929

#TimeUsernameProblemLanguageResultExecution timeMemory
873929noiaintCurtains (NOI23_curtains)C++17
100 / 100
781 ms154564 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define getbit(x, i) (((x) >> (i)) & 1) #define bit(x) (1 << (x)) #define popcount __builtin_popcountll mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); long long rand(long long l, long long r) { return l + rd() % (r - l + 1); } const int N = 1e6 + 5; const int mod = 1e9 + 7; // 998244353; const int lg = 25; // lg + 1 const int inf = 1e9; // INT_MAX; const long long llinf = 1e18; // LLONG_MAX; template<class X, class Y> bool minimize(X &a, Y b) { return a > b ? (a = b, true) : false; } template<class X, class Y> bool maximize(X &a, Y b) { return a < b ? (a = b, true) : false; } template<class X, class Y> bool add(X &a, Y b) { a += b; while (a >= mod) a -= mod; while (a < 0) a += mod; return true; } struct node { int L, R, M, val; int lazy = 0; node *l, *r; node (int _L, int _R) : L(_L), R(_R) { M = (L + R) >> 1; val = 0; if (L < R) { l = new node(L, M); r = new node(M + 1, R); } } void down() { l->lazy = max(l->lazy, lazy); r->lazy = max(r->lazy, lazy); l->val = max(l->val, lazy); r->val = max(r->val, lazy); } void update(int u, int v, int c) { if (v < L || u > R) return; if (u <= L && R <= v) { lazy = max(lazy, c); val = max(val, c); return; } down(); l->update(u, v, c); r->update(u, v, c); val = min(l->val, r->val); } int get(int u, int v) { if (v < L || u > R) return inf; if (u <= L && R <= v) return val; down(); return min(l->get(u, v), r->get(u, v)); } } *root; struct SegmentTree { int n; vector<int> val, lazy; void init(int _n) { n = _n; val.assign(n * 4 + 5, 0); lazy.assign(n * 4 + 5, 0); } void down(int i) { for (int j = i * 2; j <= i * 2 + 1; ++j) { val[j] = max(val[j], lazy[i]); lazy[j] = max(lazy[j], lazy[i]); } } void update(int i, int L, int R, int l, int r, int c) { if (r < L || l > R) return; if (l <= L && R <= r) { val[i] = max(val[i], c); lazy[i] = max(lazy[i], c); return; } down(i); int M = (L + R) >> 1; update(i << 1, L, M, l, r, c); update(i << 1 | 1, M + 1, R, l, r, c); val[i] = min(val[i << 1], val[i << 1 | 1]); } int get(int i, int L, int R, int l, int r) { if (r < L || l > R) return inf; if (l <= L && R <= r) return val[i]; down(i); int M = (L + R) >> 1; return min(get(i << 1, L, M, l, r), get(i << 1 | 1, M + 1, R, l, r)); } void update(int l, int r, int c) { update(1, 1, n, l, r, c); } int get(int l, int r) { return get(1, 1, n, l, r); } } t; int n, m, q; vector<int> curtain[N]; vector<pair<int, int> > query[N]; int ans[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> q; for (int i = 1; i <= m; ++i) { int l, r; cin >> l >> r; curtain[r].push_back(l); } for (int i = 1; i <= q; ++i) { int s, e; cin >> s >> e; query[e].emplace_back(s, i); } t.init(n); root = new node(1, n); for (int r = 1; r <= n; ++ r) { for (int l : curtain[r]) { // root->update(l, r, l); t.update(l, r, l); } for (auto [l, id] : query[r]) { // ans[id] = root->get(l, r) >= l; ans[id] = t.get(l, r) >= l; } } for (int i = 1; i <= q; ++i) cout << (ans[i] ? "YES" : "NO") << '\n'; // for (int i = 1; i <= n; ++i) // cout << root->get(i, i) << ' '; 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...