제출 #439351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
439351		pauloamed	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	492 ms	186412 KiB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
#define MAXV 123456
typedef long long ll;
using namespace std;


template<int MAXN>
struct ImplicitSegtree{
  struct Node {
  	int val, lazy; // val and lazy values
    int tl, tr; // left and right range
    int l, r; // left and right childs ids
  	Node() : val(0), lazy(0), l(-1), r(-1) {}
  };

  Node segtree[64 * MAXN];
  int nodeCount = 2;

  int merge(int a, int b){
    return 0;
  }

  void createChild(int parentNode, int childTl, int childTr, bool isLeft){
    int newNode = getNextId();
    if(isLeft) segtree[parentNode].l = newNode;
    else segtree[parentNode].r = newNode;
    segtree[newNode].tl = childTl;
    segtree[newNode].tr = childTr;
  }

  inline int getNextId(){ return nodeCount++; }

  ImplicitSegtree(){
    segtree[1].val = 0; segtree[1].lazy = 0;
    segtree[1].tl = 1; segtree[1].tr = 1e9;
  }

  void push_lazy(int node) {
  	if (segtree[node].lazy) {
  		segtree[node].val = segtree[node].tr - segtree[node].tl + 1;
  		int mid = (segtree[node].tl + segtree[node].tr) / 2;

  		if (segtree[node].l == -1) {
        createChild(node, segtree[node].tl, mid, true);
  		}
  		if (segtree[node].r == -1) {
        createChild(node, mid + 1, segtree[node].tr, false);
  		}
  		segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
  		segtree[node].lazy = 0;
  	}
  }

  void update(int node, int l, int r) {
  	push_lazy(node);
  	if (l == segtree[node].tl && r == segtree[node].tr) {
  		segtree[node].lazy = 1;
  		push_lazy(node);
  	} else {
  		int mid = (segtree[node].tl + segtree[node].tr) / 2;
  		if (segtree[node].l == -1) {
  			segtree[node].l = getNextId();
  			segtree[segtree[node].l].tl = segtree[node].tl;
  			segtree[segtree[node].l].tr = mid;
  		}
  		if (segtree[node].r == -1) {
  			segtree[node].r = getNextId();
  			segtree[segtree[node].r].tl = mid + 1;
  			segtree[segtree[node].r].tr = segtree[node].tr;
  		}

  		if (l > mid) update(segtree[node].r, l, r);
  		else if (r <= mid) update(segtree[node].l, l, r);
  		else {
  			update(segtree[node].l, l, mid);
  			update(segtree[node].r, mid + 1, r);
  		}

  		push_lazy(segtree[node].l);
  		push_lazy(segtree[node].r);
  		segtree[node].val = segtree[segtree[node].l].val + segtree[segtree[node].r].val;
  	}
  }

  int query(int node, int l, int r) {
  	push_lazy(node);
  	if (l == segtree[node].tl && r == segtree[node].tr)
      return segtree[node].val;
  	else {
  		int mid = (segtree[node].tl + segtree[node].tr) / 2;
  		if (segtree[node].l == -1) {
  			segtree[node].l = getNextId();
  			segtree[segtree[node].l].tl = segtree[node].tl;
  			segtree[segtree[node].l].tr = mid;
  		}
  		if (segtree[node].r == -1) {
  			segtree[node].r = getNextId();
  			segtree[segtree[node].r].tl = mid + 1;
  			segtree[segtree[node].r].tr = segtree[node].tr;
  		}

  		if (l > mid) return query(segtree[node].r, l, r);
  		else if (r <= mid) return query(segtree[node].l, l, r);
  		else return query(segtree[node].l, l, mid) + query(segtree[node].r, mid + 1, r);
  	}
  }
};

ImplicitSegtree<MAXV> st;
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int m;
	cin >> m;



	int c = 0;
	FOR(_, 0, m) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 1) {
			c = st.query(1, x + c, y + c);
			cout << c << '\n';
		} else st.update(1, x + c, y + c);
	}
	return 0;
}

• Subtask 1: 100 / 100