답안 #439353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
439353 2021-06-29T17:07:29 Z pauloamed 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
465 ms 186404 KB
#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;
  }

  void maybeCreateChilds(int node){
    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);
    }
  }

  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;
      maybeCreateChilds(node);
  		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;
      maybeCreateChilds(node);

  		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;
      maybeCreateChilds(node);

  		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;
}

Compilation message

apple.cpp: In instantiation of 'void ImplicitSegtree<MAXN>::push_lazy(int) [with int MAXN = 123456]':
apple.cpp:84:4:   required from 'int ImplicitSegtree<MAXN>::query(int, int, int) [with int MAXN = 123456]'
apple.cpp:112:32:   required from here
apple.cpp:54:9: warning: unused variable 'mid' [-Wunused-variable]
   54 |     int mid = (segtree[node].tl + segtree[node].tr) / 2;
      |         ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 185812 KB Output is correct
2 Correct 83 ms 185732 KB Output is correct
3 Correct 79 ms 185852 KB Output is correct
4 Correct 92 ms 185796 KB Output is correct
5 Correct 96 ms 185764 KB Output is correct
6 Correct 92 ms 185800 KB Output is correct
7 Correct 95 ms 185760 KB Output is correct
8 Correct 206 ms 185916 KB Output is correct
9 Correct 363 ms 186184 KB Output is correct
10 Correct 362 ms 186160 KB Output is correct
11 Correct 352 ms 186192 KB Output is correct
12 Correct 379 ms 186276 KB Output is correct
13 Correct 312 ms 186308 KB Output is correct
14 Correct 321 ms 186300 KB Output is correct
15 Correct 465 ms 186316 KB Output is correct
16 Correct 431 ms 186308 KB Output is correct
17 Correct 324 ms 186404 KB Output is correct
18 Correct 326 ms 186400 KB Output is correct
19 Correct 453 ms 186308 KB Output is correct
20 Correct 413 ms 186304 KB Output is correct