Submission #983534

#TimeUsernameProblemLanguageResultExecution timeMemory
983534THXuanCurtains (NOI23_curtains)C++14
100 / 100
927 ms83276 KiB
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <set> #include <map> #define INF 1e9 using namespace std; typedef long long ll; vector<int>v[500005]; vector<pair<int, int>>a[500005]; const int MAXN = 1e6 + 5; ll t[4 * MAXN], lazy[4 * MAXN]; void pushdown(int v) { if (lazy[v] > 0) { lazy[2 * v] = max(lazy[2*v], lazy[v]); lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]); t[2 * v] = max(t[2 * v], lazy[v]); t[2 * v + 1] = max(t[2 * v + 1], lazy[v]); lazy[v] = 0; } } void upd(int v, int l, int r, int tl, int tr, ll val) { if (l > r)return; if (l == tl && r == tr) { lazy[v] = max(lazy[v], val); t[v] = max(t[v], val); return; } pushdown(v); int tm = (tl + tr) / 2; upd(2 * v, l, min(r, tm), tl, tm, val); upd(2 * v + 1, max(l, tm + 1), r, tm + 1, tr, val); t[v] = min(t[v * 2], t[v * 2 + 1]); } ll query(int v, int tl, int tr, int l, int r) { if (l > r)return INF; if (l == tl && r == tr)return t[v]; pushdown(v); int tm = (tl + tr) / 2; return min(query(2 * v, tl, tm, l, min(r, tm)), query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)); } void solve() { int n, m, q; cin >> n >> m >> q; vector<int>ans(q); for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; v[r].push_back(l); } for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; a[r].push_back({ l, i }); } for (int i = 1; i <= n; i++) { for (auto l : v[i]) { upd(1, l, i, 1, n, l); //cout << query(1, 1,n, l, i) << "\n"; } for (auto l : a[i]) { if (query(1, 1, n, l.first, i) < l.first) ans[l.second] = 0; else ans[l.second] = 1; } } for (int i = 0; i < q; i++) { if (ans[i]) cout << "YES" << "\n"; else cout << "NO" << "\n"; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1;// cin>>t; while (t--) solve(); 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...