Submission #1314642

#TimeUsernameProblemLanguageResultExecution timeMemory
1314642joshjuiceCurtains (NOI23_curtains)C++20
100 / 100
720 ms115748 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
#define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--))
#define all(a) a.begin(), a.end()
#define ppf pop_front
#define ppb pop_back
#define pf push_front
#define pb push_back
#define fr first
#define sc second
#define ii pair<int, int>
#define iii tuple<int, int, int>
#define vc vector
#define sz(a) a.size()
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)
#define setval(arr, x) memset(arr, x, sizeof(arr))

template<typename T>
using vv = vc<vc<T>>;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAX = 5e5+5;

bool cmp(ii A, ii B) { return A.sc < B.sc; }

int N, M, Q;
int ans[MAX];

struct Node {
  Node *l = nullptr, *r = nullptr;
  int s, e, m, rend, act = 0;
  int lazy_left = -1, lazy_right = -1;
  Node(int S, int E) {
    s = S, e = E, m = (s + e) >> 1;
    if (s != e) {
      l = new Node(s, m);
      r = new Node(m+1, e);
    } else rend = s-1;
  }
  void update_lazy(int ul, int ur) {
    if (lazy_left == -1 || ul <= lazy_left) {
      lazy_left = ul;
      lazy_right = ur;
    } else if (ul <= lazy_right) {
      lazy_right = ur;
    }
  }
  void prop() {
    if (lazy_left == -1) return;
    l->update_lazy(lazy_left, lazy_right);
    r->update_lazy(lazy_left, lazy_right);
    lazy_left = lazy_right = -1;
  }
  void update(int L, int R, int ul, int ur) {
    if (s > R || e < L) return;
    if (L <= s && e <= R) {
      update_lazy(ul, ur);
      return;
    }
    prop();
    l->update(L, R, ul, ur);
    r->update(L, R, ul, ur);
  }
  ii query(int x) {
    if (s == e) {
      if (lazy_left != -1) {
        if (rend >= lazy_left) {
          mxto(rend, lazy_right);
          act = 1;
        }
        lazy_left = lazy_right = -1;
      }
      return ii(rend, act);
    } else {
      ii a;
      if (x <= m) a = l->query(x);
      else a = r->query(x);
      if (lazy_left != -1) {
        if (a.fr >= lazy_left) {
          mxto(a.fr, lazy_right);
          a.sc = 1;
        }
      }
      return a;
    }
  }
} *root;

struct op {
  int typ, l, r, idx;
  op(int _t, int _l, int _r, int _i) {
    typ = _t, l = _l, r = _r, idx = _i;
  }
  bool operator<(const op &other) const {
    return r < other.r || (r == other.r && typ < other.typ);
  }
};

int32_t main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> N >> M >> Q;
  vc<op> v;
  v.reserve(M+Q);
  int X, Y;
  rep(i, 1, M+1) cin >> X >> Y, v.pb(op(0, X, Y, i));
  rep(i, 1, Q+1) cin >> X >> Y, v.pb(op(1, X, Y, i));
  sort(all(v));
  root = new Node(1, N);
  for (auto it : v) {
    if (it.typ == 0) root->update(1, it.l, it.l-1, it.r);
    else {
      ii far = root->query(it.l);
      if (far.fr == it.r && far.sc == 1) ans[it.idx] = 1;
      else ans[it.idx] = 0;
    }
  }
  rep(i, 1, Q+1) cout << (ans[i] ? "YES\n" : "NO\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...