제출 #1314900

#제출 시각아이디문제언어결과실행 시간메모리
1314900baodatCurtains (NOI23_curtains)C++20
44 / 100
1590 ms19644 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define FOR(i, l, r) for(int i = l; i <= r; i++) #define FORD(i, l, r) for(int i = l; i >= r; i--) #define db double #define ldb long double #define all_1(x) (x).begin() + 1, (x).end() #define all(x) (x).begin(), (x).end() #define ins insert #define pb push_back int n, m, q; struct segment_tree{ int _n; vector<int> _st; segment_tree(int n = 0){ init(n); } void init(int n){ _n = n; _st.assign(4 * _n + 5, -2e9); } void update(int i, int l, int r, int pos, int val){ if(pos > r || pos < l) return; if(l == r){ _st[i] = max(_st[i], val); return; } int m = (l + r) >> 1, cl = (i << 1), cr = (cl | 1); update(cl, l, m, pos, val); update(cr, m + 1, r, pos, val); _st[i] = max(_st[cl], _st[cr]); } int query(int i, int l, int r, int u, int v){ if(l > v || r < u) return -2e9; if(l >= u && r <= v) return _st[i]; int m = (l + r) >> 1, cl = (i << 1), cr = (cl | 1); return max(query(cl, l, m, u, v), query(cr, m + 1, r, u, v)); } }; struct Data{ int from, to, id; }; void solve(){ cin >> n >> m >> q; vector<pair<int, int>> curtain(m + 1); FOR(i, 1, m) cin >> curtain[i].first >> curtain[i].second; vector<Data> queries(q + 1); FOR(i, 1, q) cin >> queries[i].from >> queries[i].to, queries[i].id = i; sort(all_1(curtain), [&](pair<int, int> a, pair<int, int> b){ return a.second < b.second || (a.second == b.second && a.first < b.first); }); sort(all_1(queries), [&](Data a, Data b){ return a.to < b.to || (a.to == b.to && a.from < b.from); }); segment_tree st(n); vector<bool>ans(q + 1); int j = 1; FOR(qr, 1, q){ auto [from, to, id] = queries[qr]; while(j <= m && curtain[j].second <= to){ st.update(1, 1, n, curtain[j].first, curtain[j].second); ++j; } int i = from; bool ok = true; while(i <= to){ int maxi = st.query(1, 1, n, from, i); if(maxi < i){ ok = false; break; } i = maxi + 1; } ans[id] = ok; } FOR(i, 1, q) cout << (ans[i] ? "YES\n" : "NO\n"); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } return 0; } /* n san khau, m man man i che l[i] -> r[i] truy van j, yeu can che doan from[j] -> to[j] from[j] -> to[j] l[i] < from[j] || r[i] > to[j] -> continue => l[i] >= from[j] && r[i] <= to[j] -> thang nao cung dc gia su ta co dinh dc to[j] chi quan tam max cua r[j], */
#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...