Submission #439351

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
439351	2021-06-29T17:04:52 Z	pauloamed	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	492 ms	186412 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;
  }

  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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	185796 KB	Output is correct
2	Correct	78 ms	185836 KB	Output is correct
3	Correct	76 ms	185808 KB	Output is correct
4	Correct	91 ms	185796 KB	Output is correct
5	Correct	100 ms	185828 KB	Output is correct
6	Correct	92 ms	185812 KB	Output is correct
7	Correct	95 ms	185776 KB	Output is correct
8	Correct	206 ms	186032 KB	Output is correct
9	Correct	337 ms	186108 KB	Output is correct
10	Correct	394 ms	186344 KB	Output is correct
11	Correct	438 ms	186192 KB	Output is correct
12	Correct	385 ms	186188 KB	Output is correct
13	Correct	348 ms	186224 KB	Output is correct
14	Correct	322 ms	186268 KB	Output is correct
15	Correct	452 ms	186412 KB	Output is correct
16	Correct	492 ms	186268 KB	Output is correct
17	Correct	354 ms	186276 KB	Output is correct
18	Correct	339 ms	186264 KB	Output is correct
19	Correct	483 ms	186328 KB	Output is correct
20	Correct	458 ms	186372 KB	Output is correct