Submission #1141327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141327		yytsi	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	381 ms	327524 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 = (r - l + 1);
    // if this is a leaf node, we don't need to push to children
    if (l == r) return;
    makeLeft();
    makeRight();
    left->lazy = 1;
    right->lazy = 1;
  }

  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; // no overlap

  // if fully covered
  if (x <= cur->l && cur->r <= y) {
    cur->lazy  = 1;
    cur->value = (cur->r - cur->l + 1);
    return;
  }

  if (cur->lazy == 1) {
    cur->makeLeft();
    cur->makeRight();
    cur->left->lazy  = 1;
    cur->right->lazy = 1;
    cur->left->value  = (cur->left->r  - cur->left->l  + 1);
    cur->right->value = (cur->right->r - cur->right->l + 1);
    cur->lazy = 0;
  }

  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();
  cur->pushLazy();
  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+20);

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

• Subtask 1: 0 / 100