Submission #1299926

#TimeUsernameProblemLanguageResultExecution timeMemory
1299926danglayloi1Curtains (NOI23_curtains)C++20
100 / 100
861 ms82412 KiB
#include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=5e5+5; const int LG=20; int n, m, q, nod[nx<<2], la[nx<<2]; vector<int> ve[nx]; vector<ii> f[nx]; string ans[nx]; void down(int id) { if(la[id]==-inf) return; for(int j = id*2; j <= id*2+1; j++) la[j]=max(la[j], la[id]), nod[j]=max(nod[j], la[id]); la[id]=-inf; } void update(int id, int l, int r, int u, int v, int val) { if(l>v || r<u) return; if(l>=u && r<=v) { la[id]=max(la[id], val); nod[id]=max(nod[id], val); return; } int mid=(l+r)>>1; down(id); update(id<<1, l, mid, u, v, val); update(id<<1|1, mid+1, r, u, v, val); nod[id]=min(nod[id<<1], nod[id<<1|1]); } int get(int id, int l, int r, int u, int v) { if(l>v || r<u) return inf; if(l>=u && r<=v) return nod[id]; int mid=(l+r)>>1; down(id); return min(get(id<<1, l, mid, u, v), get(id<<1|1, mid+1, r, u, v)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q; while(m--) { int l, r; cin>>l>>r; ve[r].emplace_back(l); } for(int i = 1; i <= q; i++) { int l, r; cin>>l>>r; f[r].emplace_back(l, i); } memset(la, -0x3f, sizeof(la)); memset(nod, -0x3f, sizeof(nod)); for(int i = 1; i <= n; i++) { for(int x:ve[i]) update(1, 1, n, x, i, x); for(auto it:f[i]) ans[it.se]=(get(1, 1, n, it.fi, i)>=it.fi)?"YES":"NO"; } for(int i = 1; i <= q; i++) cout<<ans[i]<<'\n'; }
#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...