Submission #1169748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169748		huutuan	Curtains (NOI23_curtains)	C++20	100 / 100	636 ms	72560 KiB

curtains

#include<bits/stdc++.h>
#define taskname "curtains"

using namespace std;

struct Node{
   int val, lazy;
   Node (int x=-1, int y=0){
      val=x;
      lazy=y;
   }
   friend Node operator+(const Node &a, const Node &b){
      return Node(min(a.val, b.val));
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void apply(int k, int val){
      t[k].val=max(t[k].val, val);
      t[k].lazy=max(t[k].lazy, val);
   }
   void push(int k){
      apply(k<<1, t[k].lazy);
      apply(k<<1|1, t[k].lazy);
      t[k].lazy=0;
   }
   void update(int k, int l, int r, int L, int R, int val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, val);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   int get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return 1e9;
      if (L<=l && r<=R) return t[k].val;
      push(k);
      int mid=(l+r)>>1;
      return min(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
   }
} st;

const int N=5e5+1;
int n, m, q, l[N], r[N], deg[N], block[N], ans[N];
vector<pair<int, int>> vq[N];
vector<int> vr[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   // freopen(taskname".inp", "r", stdin);
   // freopen(taskname".out", "w", stdout);
   cin >> n >> m >> q;
   for (int i=1; i<=m; ++i){
      cin >> l[i] >> r[i];
      vr[r[i]].emplace_back(l[i]);
   }
   for (int i=1; i<=q; ++i){
      int x, y;
      cin >> x >> y;
      vq[y].emplace_back(x, i);
   }
   st.init(n);
   for (int i=1; i<=n; ++i){
      for (int j:vr[i]) st.update(1, 1, n, j, i, j);
      for (auto &j:vq[i]) ans[j.second]=st.get(1, 1, n, j.first, i)>=j.first;
   }
   for (int i=1; i<=q; ++i) cout << (ans[i]?"YES\n":"NO\n");
   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