teamscode summer 2022 highways tester solution

#include <bits/stdc++.h>
using namespace std;

template<int N_>
struct Lst {
  int n, t[N_ * 2], z[N_];

  void bld(int n_) {
    n = n_;
  }
  void pul(int k, int, int) {
    int lc = k << 1 | 0, rc = k << 1 | 1;
    t[k] = min(t[lc], t[rc]);
  }
  void put(int k, int l, int r, int x) {
    t[k] = x;
    if (l != r)
      z[k] = x;
  }
  void pus(int k, int l, int r) {
    if (z[k] != 0) {
      int m = (l + r) / 2;
      put(k << 1 | 0, l, m, z[k]), put(k << 1 | 1, m + 1, r, z[k]);
      z[k] = 0;
    }
  }
  void upd(int k, int l, int r, int ql, int qr, int x) {
    if (ql <= l && qr >= r)
      put(k, l, r, x);
    else if (qr >= l && ql <= r) {
      int m = (l + r) / 2;
      pus(k, l, r);
      upd(k << 1 | 0, l, m, ql, qr, x), upd(k << 1 | 1, m + 1, r, ql, qr, x);
      pul(k, l, r);
    }
  }
  void upd(int l, int r, int x) {
    upd(1, 0, n - 1, l, r, x);
  }
  int qry(int k, int l, int r, int ql, int qr) {
    if (qr < l || ql > r)
      return INT_MAX;
    else if (ql <= l && qr >= r)
      return t[k];
    else {
      int m = (l + r) / 2;
      pus(k, l, r);
      return min(qry(k << 1 | 0, l, m, ql, qr), qry(k << 1 | 1, m + 1, r, ql, qr));
    }
  }
  int qry(int l, int r) {
    return qry(1, 0, n - 1, l, r);
  }
};

Lst<1 << 18> st;

int main() {
  int n, m, k, q;
  scanf("%d%d%d%d", &n, &m, &k, &q);
  vector<tuple<int, int, int>> rd(k);
  for (auto &[y, x1, x2] : rd)
    scanf("%d%d%d", &x1, &x2, &y);
  vector<tuple<int, int, int, int, int>> qy;
  for (int h = 0; h < q; h++) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if (y1 > y2)
      swap(y1, y2);
    if (x1 > x2)
      swap(x1, x2);
    qy.push_back({y2, x2, y1, x1, h});
  }
  sort(rd.begin(), rd.end());
  sort(qy.begin(), qy.end());
  int i = 0;
  st.bld(m + 1);
  vector<bool> ans(q);
  for (auto [y2, x2, y1, x1, h] : qy) {
    while (i < k && get<0>(rd[i]) <= y2) {
      st.upd(get<1>(rd[i]), get<2>(rd[i]) - 1, get<0>(rd[i]));
      i++;
    }
    ans[h] = x1 == x2 || st.qry(x1, x2 - 1) >= y1;
  }
  for (bool x : ans)
    printf(x ? "YES\n" : "NO\n");
  return 0;
}