Submission #1141306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141306		yytsi	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	0 ms	320 KiB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int q;
ll c;

struct node {
  ll l, r, value, lazy;
  node *left, *right;
  node(ll l, ll r) : l(l), r(r), value(0), lazy(0), left(nullptr), right(nullptr) {}
  
  void pushLazy() {
    if (lazy == 0) return;
    // lazy must be applied to this node
    // and then pushed to children
    value += lazy;
    // if this is a leaf node, we don't need to push to children
    if (l == r) return;
    makeLeft();
    makeRight();
    left->lazy += lazy;
    right->lazy += lazy;
    lazy = 0;
  }

  void makeLeft() {
    if (left == nullptr) left = new node(l, (l+r)/2);
  }

  void makeRight() {
    if (right == nullptr) right = new node((l+r)/2+1, r);
  }
};

void addToRange(node *cur, ll x, ll y) {
  if (cur->l > y || cur->r < x) return;
  if (x <= cur->l && cur->r <= y) {
    // node fully inside range
    cur->lazy = 1;
    cur->pushLazy();
    return;
  }
  cur->pushLazy();
  cur->makeLeft();
  cur->makeRight();
  addToRange(cur->left, x, y);
  addToRange(cur->right, x, y);
  cur->value = cur->left->value + cur->right->value;
}

ll getSum(node *cur, ll x, ll y) {
  if (cur-> l > y || cur->r < x) return 0;
  cur->pushLazy();
  if (x <= cur->l && cur->r <= y) return cur->value;
  cur->makeLeft();
  cur->makeRight();
  return getSum(cur->left, x, y) + getSum(cur->right, x, y);
}

// 0 1 2 3 4
// [0, 3]
// m = (3+0)/2 = 1
// [2,3] [m+1, r]

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>q;

  node* root = new node(0, 1e9);

  for (int i = 0; i < q; i++) {
    int d; ll x, y;
    cin>>d>>x>>y;
    if (d == 2) {
      addToRange(root, x, y);
    } else {
      c = getSum(root, x, y);
      cout<<c<<'\n';
    }
  }
}

• Subtask 1: 0 / 100