Submission #1029247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029247		ihne	Curtains (NOI23_curtains)	C++17	100 / 100	486 ms	101156 KiB

curtains

#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=5e5+5;
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 (q.empty()) return;
  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>=l;i--){
    f[i]=1000000000;
    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++){
      |                ~^~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20