제출 #1243331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243331		lorewired	원숭이와 사과 나무 (IZhO12_apple)	C++20	0 / 100	0 ms	328 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 = 4e6;
  
  int N; cin >> N;

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

  vector<node> seg(1);
  seg.reserve(mxN);

  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) * seg[u].la;
    sp(u);
    seg[seg[u].lf].la += seg[u].la;
    seg[seg[u].rg].la += seg[u].la;
    seg[u].la = 0;
  };

  function<void(int, int, int, int, int)> modify = [&] (int u, int l, int r, int l2, int r2) {
    if (l > r2 || r < l2) return;
    lazy(u, l, r);
    if (l >= l2 && r <= r2) {
      seg[u].la++;
      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) {
    if (l > r2 || r < l2) return 0LL;
    lazy(u, l, r);
    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, 0, mxN, x + ans, y + ans);
    } else {
      ans = query(0, 0, mxN, x + ans, y + ans);
      cout << ans << '\n';
    }
  }

  return 0;
}

• Subtask 1: 0 / 100