Submission #1184909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184909		epicci23	Curtains (NOI23_curtains)	C++20	100 / 100	808 ms	82872 KiB

curtains

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 5e5 + 5;
const int INF = 1e18;

int lazy[4*N], mn[4*N], mx[4*N];

void build(int rt,int l,int r){
  mn[rt] = mx[rt] = INF;
  if(l == r) return;
  int mid = (l + r) / 2;
  build(rt * 2, l, mid), build(rt * 2 + 1, mid + 1, r);
}

inline void push(int rt,int l,int r){
  if(!lazy[rt]) return;
  mn[rt] = mx[rt] = lazy[rt];
  if(l == r){
  	lazy[rt] = 0;
  	return;
  }
  lazy[rt * 2] = lazy[rt * 2 + 1] = lazy[rt];
  lazy[rt] = 0;
}


void upd(int rt,int l,int r,int gl,int gr,int u){
  push(rt, l, r);
  if(r < gl || l > gr || mx[rt] <= u) return;
  if(l >= gl && r <= gr && mn[rt] >= u){
   lazy[rt] = u;
   push(rt, l, r);
   return;
  }

  int mid = (l + r) / 2;
  upd(rt * 2, l, mid, gl, gr, u);
  upd(rt * 2 + 1, mid + 1, r, gl, gr, u);

  mn[rt] = min(mn[rt * 2], mn[rt * 2 + 1]);
  mx[rt] = max(mx[rt * 2], mx[rt * 2 + 1]);
}

int query_min(int rt,int l,int r,int gl,int gr){
  push(rt, l, r);
  if(r < gl || l > gr) return INF;
  if(l >= gl && r <= gr) return mn[rt];
  int mid = (l + r) / 2;
  return min(query_min(rt * 2, l, mid, gl, gr), query_min(rt * 2 + 1, mid + 1, r, gl, gr));
}

int query_max(int rt,int l,int r,int gl,int gr){
  push(rt, l, r);
  if(r < gl || l > gr) return -INF;
  if(l >= gl && r <= gr) return mx[rt];
  int mid = (l + r) / 2;
  return max(query_max(rt * 2, l, mid, gl, gr), query_max(rt * 2 + 1, mid + 1, r, gl, gr));
}

void _(){
  int n, m, q;
  cin >> n >> m >> q;

  vector<int> Perde[n+5];
  for(int i=1;i<=m;i++){
    int l, r;
    cin >> l >> r;
    Perde[l].push_back(r);
  }

  vector<array<int,2>> Query[n+5];
  vector<int> ans(q+5,0);
  for(int i=1;i<=q;i++){
    int l, r;
    cin >> l >> r;
    Query[l].push_back({r, i});
  }

  build(1, 1, n);

  for(int i=n;i>=1;i--){
    for(int u : Perde[i]) upd(1,1,n,i,u,u);

    for(auto [u, ind] : Query[i]){
      int xd = query_max(1, 1, n, i, u);
      if(xd > u) ans[ind] = 0;
      else ans[ind] = 1;
    }
  }

  for(int i=1;i<=q;i++){
     if(ans[i]) cout << "YES\n";
     else cout << "NO\n";
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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