Submission #1243307

#TimeUsernameProblemLanguageResultExecution timeMemory
1243307lorewiredMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
0 ms324 KiB
#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 = 4e7+9;
  
  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 lazy = [&] (int u, int l, int r) {
    if (!seg[u].la) return;
    seg[u].s += (r - l + 1) * seg[u].la;
    if (l != r) {
      if (!seg[u].lf) seg[u].lf = create();
      if (!seg[u].rg) seg[u].rg = create();
      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;
    if (!seg[u].lf) seg[u].lf = create();
    if (!seg[u].rg) seg[u].rg = create();
    modify(seg[u].lf, l, m, l2, r2);
    modify(seg[u].rg, m+1, r, l2, r2);
    seg[u].s = (seg[u].lf ? seg[seg[u].lf].s : 0) + (seg[u].rg ? seg[seg[u].rg].s : 0);
  };

  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;
    return (seg[u].lf ? query(seg[u].lf, l, m, l2, r2) : 0) + (seg[u].rg ? query(seg[u].rg, m+1, r, l2, r2) : 0);
  };

  int ans = 0;
  
  for (int i = 0; i < N; i++) {
    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...