Submission #1280870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280870		aeg	Curtains (NOI23_curtains)	C++20	100 / 100	594 ms	33732 KiB

curtains

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

struct segtr {
  vector<pair<int, int>> lz;
  int n;
  segtr(int n) : lz(n << 2, {INT_MAX, INT_MAX}), n(n) {}

  pair<int, int> unite(pair<int, int> l, pair<int, int> r) {
    if (l.second > r.second)
      swap(l, r);
    if (r.first == INT_MAX)
      return l;
    if (l.second >= r.first - 1)
      return {min(l.first, r.first), r.second};
    return l;
  }

  void pushdown(int ind) {
    lz[ind << 1] = unite(lz[ind << 1], lz[ind]);
    lz[ind << 1 | 1] = unite(lz[ind << 1 | 1], lz[ind]);
    lz[ind] = {INT_MAX, INT_MAX};
  }

  void update(int ind, int l, int r, int tl, int tr, int x, int y) {
    if (x > tr || y < tl)
      return;
    if (x <= tl && tr <= y) {
      lz[ind] = unite(lz[ind], {l, r});
      return;
    }
    pushdown(ind);
    int m = (tl + tr) >> 1;
    if (x <= m)
      update(ind << 1, l, r, tl, m, x, y);
    if (y > m)
      update(ind << 1 | 1, l, r, m + 1, tr, x, y);
  }

  void upd(int l, int r) { update(1, l, r, 0, n - 1, 0, l); }

  int quer(int ind, int l, int r, int pos) {
    if (l == r) {
      if (pos >= lz[ind].first)
        return lz[ind].second;
      else
        return pos - 1;
    }
    pushdown(ind);
    int m = (l + r) >> 1;
    if (pos <= m)
      return quer(ind << 1, l, m, pos);
    else
      return quer(ind << 1 | 1, m + 1, r, pos);
  }

  int query(int pos) { return quer(1, 0, n - 1, pos); }
};

struct quer {
  int l, r;
  bool typ;
  int ind;
  quer(int l = 0, int r = 0, bool typ = false, int ind = 0)
      : l(l), r(r), typ(typ), ind(ind) {}
};

bool operator<(quer const &q1, quer const &q2) {
  if (q1.r != q2.r)
    return q1.r < q2.r;
  else if (q1.typ != q2.typ) {
    if (q1.typ)
      return false;
    return true;
  }

  else if (q1.l != q2.l)
    return q1.l < q2.l;
  else
    return q1.ind < q2.ind;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m, q;
  cin >> n >> m >> q;
  vector<bool> ans(q, false);
  segtr tr(n);

  vector<quer> qs;
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    qs.emplace_back(l, r, false, i);
  }
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    qs.emplace_back(l, r, true, i);
  }
  sort(qs.begin(), qs.end());
  for (int i = 0; i < q + m; i++) {
    if (qs[i].typ) {
      int anss = tr.query(qs[i].l);
      // cout << anss << '\n';
      // for (auto &[x, y] : tr.lz)
      //   cout << x << ' ' << y << '\n';
      // cout << '\n';
      if (anss == qs[i].r)
        ans[qs[i].ind] = true;
    } else {
      tr.upd(qs[i].l, qs[i].r);
    }
  }

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

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