Submission #439353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
439353	2021-06-29T17:07:29 Z	pauloamed	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	465 ms	186404 KB

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

  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;
      |         ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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