Submission #1335037

#TimeUsernameProblemLanguageResultExecution timeMemory
1335037kunzaZa183원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
2097 ms42320 KiB
#include <bits/stdc++.h>
using namespace std;
const int mn = 3.5e6;
int l[mn], r[mn], val[mn];
bitset<mn> bs;

int tot = 0;
int nw() {
  l[tot] = -1, r[tot] = -1, val[tot] = 0;
  if (tot >= mn) {
    while (1) {
    }
  }
  return tot++;
}

void lzy(int cin, int cl, int cr) {
  if (bs[cin]) {
    val[cin] = cr - cl + 1;
    if (cl == cr) {
      return;
    }
    if (l[cin] == -1) {
      l[cin] = nw(), r[cin] = nw();
    }

    bs[l[cin]] = bs[r[cin]] = 1;
  }
}

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

  if (ql <= cl && cr <= qr) {
    bs[cin] = 1;
    lzy(cin, cl, cr);
    return;
  }

  if (l[cin] == -1) {
    l[cin] = nw(), r[cin] = nw();
  }

  upd(l[cin], cl, (cl + cr) / 2, ql, qr);
  upd(r[cin], (cl + cr) / 2 + 1, cr, ql, qr);

  val[cin] = val[l[cin]] + val[r[cin]];
}

int qry(int cin, int cl, int cr, int ql, int qr) {
  // cout << "Q: " << cl << " " << cr << " " << ql << ' ' << qr << " " << val
  //      << " " << lz << "\n";
  lzy(cin, 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[cin];

  if (l[cin] == -1) {
    l[cin] = nw(), r[cin] = nw();
  }
  int x = qry(l[cin], cl, (cl + cr) / 2, ql, qr) +
          qry(r[cin], (cl + cr) / 2 + 1, cr, ql, qr);

  // change
  val[cin] = val[l[cin]] + val[r[cin]];

  return x;
}
int main() {
  // cin.tie(0)->sync_with_stdio(0);
  int m;
  cin >> m;
  int c = 0;
  const int mn = 1e9 + 5;
  nw();
  for (int i = 0; i < m; i++) {
    int d, x, y;
    cin >> d >> x >> y;
    x += c, y += c;
    if (d == 1) {

      c = qry(0, 0, mn - 1, x, y);
      cout << c << "\n";
    } else {
      upd(0, 0, mn - 1, x, y);
    }
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...