Submission #1029229

#TimeUsernameProblemLanguageResultExecution timeMemory
1029229ihneCurtains (NOI23_curtains)C++17
0 / 100
4 ms5156 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pii pair<int,int> #define pb push_back const int mn=1e5+5; const int mod=1e9+7; struct query{ int l,r,id; }; int a[mn],ans[mn],f[mn]; vector<int> L[mn],R[mn]; void solve(int l,int r,vector<query> q){ if (l==r){ int bl=0; for (int j:L[l]) if (j==r) bl=1; for (int i=0;i<q.size();i++){ ans[q[i].id]=bl; } return; } int mid=l+r>>1; stack<int> v; for (int i=mid;i>=1;i--){ f[i]=1e9; for (int j:L[i]){ if (j>=mid) f[i]=min(f[i],j); while (!v.empty()&&v.top()-1<=j&&j<=f[v.top()]){ f[i]=min(f[i],f[v.top()]); v.pop(); } } v.push(i); } while (!v.empty()) v.pop(); for (int i=mid+1;i<=r;i++){ f[i]=0; for (int j:R[i]){ if (j<=mid+1) f[i]=max(f[i],j); while (!v.empty()&&v.top()-1>=j&&j>=f[v.top()]){ f[i]=max(f[i],f[v.top()]); v.pop(); } } v.push(i); } vector<query> vl,vr; for (int i=0;i<q.size();i++){ if (q[i].r<=mid) vl.pb(q[i]); else if (q[i].l>mid) vr.pb(q[i]); else{ if (f[q[i].l]<=q[i].r&&f[q[i].r]>=q[i].l) ans[q[i].id]=1; } } solve(l,mid,vl); solve(mid+1,r,vr); } signed main(){ //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); int n,m,Q; cin>>n>>m>>Q; for (int i=1;i<=m;i++){ int l,r; cin>>l>>r; L[l].pb(r); R[r].pb(l); } vector<query> q; for (int i=1;i<=Q;i++){ int l,r; cin>>l>>r; q.pb({l,r,i}); } solve(1,n,q); for (int i=1;i<=Q;i++){ if (ans[i]) cout<<"YES\n"; else cout<<"NO\n"; } }

Compilation message (stderr)

curtains.cpp: In function 'void solve(int, int, std::vector<query>)':
curtains.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i=0;i<q.size();i++){
      |                  ~^~~~~~~~~
curtains.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int mid=l+r>>1;
      |           ~^~
curtains.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i=0;i<q.size();i++){
      |                ~^~~~~~~~~
#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...