제출 #1330961

#제출 시각아이디문제언어결과실행 시간메모리
1330961kunzaZa183Monkey and Apple-trees (IZhO12_apple)C++20
0 / 100
420 ms265936 KiB
#include <bits/stdc++.h>
using namespace std;
struct nod {
  int val, lz;
  nod *n[2];

  nod() { val = 0, lz = 0; }

  void lzy(int cl, int cr) {
    if (lz == 1) {
      val = cr - cl + 1;
      if (!n[0]) {
        n[0] = new nod, n[1] = new nod;
      }

      n[0]->lz = n[1]->lz = 1;
    }
  }

  void upd(int cl, int cr, int ql, int qr) {
    // cout << "U: " << cl << " " << cr << " " << ql << " " << qr << "\n";
    lzy(cl, cr);
    if (ql > cr || cl > qr)
      return;

    if (ql <= cl && cr <= qr) {
      lz = 1;
      lzy(cl, cr);
      return;
    }

    if (!n[0]) {
      n[0] = new nod, n[1] = new nod;
    }

    n[0]->upd(cl, (cl + cr) / 2, ql, qr);
    n[1]->upd((cl + cr) / 2 + 1, cr, ql, qr);

    val = n[0]->val + n[1]->val;
  }

  int qry(int cl, int cr, int ql, int qr) {
    // cout << "Q: " << cl << " " << cr << " " << ql << ' ' << qr << " " << val
    //      << " " << lz << "\n";
    lzy(cl, cr);
    // cout << "Q: " << cl << " " << cr << " " << ql << ' ' << qr << " " << val
    //      << " " << lz << "\n";
    if (cl > qr || ql > cr)
      return 0;

    if (ql <= cl && cr <= qr)
      return val;

    if (!n[0]) {
      n[0] = new nod, n[1] = new nod;
    }
    int x = n[0]->qry(cl, (cl + cr) / 2, ql, qr) +
            n[1]->qry((cl + cr) / 2 + 1, cr, ql, qr);

    val = n[0]->val + n[1]->val;

    return x;
  }
};
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int m;
  cin >> m;
  int c = 0;
  nod *no = new nod;
  const int mn = 1e9 + 5;
  for (int i = 0; i < m; i++) {
    int d, x, y;
    cin >> d >> x >> y;
    x += c, y += c;
    if (d == 1) {
      c = no->qry(0, mn - 1, x, y);
      cout << c << "\n";
    } else {
      no->upd(0, mn - 1, x, y);
    }
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...