Submission #1243338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243338		lorebas12	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	382 ms	260520 KiB

apple

#include <bits/stdc++.h>

#define int long long
#define ar array

signed main() {
  using namespace std;
  ios_base::sync_with_stdio(false), cin.tie(nullptr);

  const int mxN = 1e9;
  
  int N; cin >> N;

  struct node {
    int la, s;
    int lf, rg;
  };

  vector<node> seg(1);
  seg.reserve(1e7+10);

  auto create = [&] () -> int {
    seg.emplace_back(node());
    return (int)seg.size() - 1;
  };

  auto sp = [&] (int u) {
    if (!seg[u].lf) seg[u].lf = create();
    if (!seg[u].rg) seg[u].rg = create();
  };
  
  auto lazy = [&] (int u, int l, int r) {
    if (!seg[u].la) return;
    seg[u].s = (r - l + 1);
    if (l != r) {
      sp(u);
      seg[seg[u].lf].la = seg[seg[u].rg].la = 1;
    }
    seg[u].la = 0;
  };

  function<void(int, int, int, int, int)> modify = [&] (int u, int l, int r, int l2, int r2) {
    lazy(u, l, r);
    if (l > r2 || r < l2) return;
    if (l >= l2 && r <= r2) {
      seg[u].la = 1;
      lazy(u, l, r);
      return;
    }
    int m = l + r >> 1;
    sp(u);
    modify(seg[u].lf, l, m, l2, r2);
    modify(seg[u].rg, m+1, r, l2, r2);
    seg[u].s = seg[seg[u].lf].s + seg[seg[u].rg].s;
  };

  function<int(int, int, int, int, int)> query = [&] (int u, int l, int r, int l2, int r2) {
    lazy(u, l, r);
    if (l > r2 || r < l2) return 0LL;
    if (l >= l2 && r <= r2) return seg[u].s;
    int m = l + r >> 1;
    int L = seg[u].lf ? query(seg[u].lf, l, m, l2, r2) : 0;
    int R = seg[u].rg ? query(seg[u].rg, m+1, r, l2, r2) : 0;
    return L + R;
  };

  int ans = 0;

  while (N--) {
    int T, x, y; cin >> T >> x >> y;
    if (T == 2) {
      modify(0, 1, mxN, x + ans, y + ans);
    } else {
      ans = query(0, 1, mxN, x + ans, y + ans);
      cout << ans << '\n';
    }
  }

  return 0;
}

• Subtask 1: 100 / 100