Submission #966341

#TimeUsernameProblemLanguageResultExecution timeMemory
966341AcanikolicCurtains (NOI23_curtains)C++14
0 / 100
8 ms26972 KiB
#include <bits/stdc++.h> #define pb push_back #define F first #define S second using namespace std; const int N = 500000 + 10; const int mod = 998244353; const int inf = 1e9; int res[N],mx[N]; vector<int>segs[N]; vector<pair<int,int>>kveri[N]; int st[N * 4],lazy[N * 4]; bool lzy[N * 4]; void push(int node,int tl,int tr) { if(!lzy[node]) return; st[node] = max(st[node],lazy[node]); if(tl != tr) { lazy[node * 2] = max(lazy[node * 2],lazy[node]); lazy[node * 2 + 1] = max(lazy[node * 2 + 1],lazy[node]); lzy[node * 2] = true; lzy[node * 2 + 1] = true; } lazy[node] = 0; lzy[node] = false; } void Set(int node,int tl,int tr,int l,int r,int x) { if(tl > r || tr < l) return; if(tl >= l && tr <= r) { lazy[node] = max(lazy[node],x); lzy[node] = true; push(node,tl,tr); return; } push(node,tl,tr); int mid = (tl + tr) / 2; Set(node * 2,tl,mid,l,r,x); Set(node * 2 + 1,mid + 1,tr,l,r,x); st[node] = min(st[node * 2],st[node * 2 + 1]); } int get(int node,int tl,int tr,int l,int r) { push(node,tl,tr); if(tl > r || tr < l) return inf; if(tl >= l && tr <= r) return st[node]; int mid = (tl + tr) / 2; return min(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r)); } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m,q; cin >> n >> m >> q; for(int i = 1; i <= m; i++) { int l,r; cin >> l >> r; segs[r].pb(l); } for(int i = 1; i <= q; i++) { int l,r; cin >> l >> r; kveri[r].pb({l,i}); } for(int i = 1; i <= n; i++) { for(auto X : segs[i]) Set(1,1,n,X,i,X); for(auto X : kveri[i]) if(get(1,1,n,X.F,i) >= X.F) res[X.S] = 1; } for(int i = 1; i <= q; i++) cout << (res[i] == 1 ? "YES\n" : "NO\n"); 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...