Submission #439348

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
439348	2021-06-29T16:59:28 Z	pauloamed	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	466 ms	188568 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;
  }

  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) {
  			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;
  		}
  		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	80 ms	185912 KB	Output is correct
2	Correct	84 ms	185756 KB	Output is correct
3	Correct	81 ms	185820 KB	Output is correct
4	Correct	95 ms	185988 KB	Output is correct
5	Correct	97 ms	186040 KB	Output is correct
6	Correct	100 ms	185924 KB	Output is correct
7	Correct	101 ms	185932 KB	Output is correct
8	Correct	222 ms	186892 KB	Output is correct
9	Correct	374 ms	187976 KB	Output is correct
10	Correct	366 ms	187896 KB	Output is correct
11	Correct	388 ms	188152 KB	Output is correct
12	Correct	380 ms	187916 KB	Output is correct
13	Correct	342 ms	188568 KB	Output is correct
14	Correct	314 ms	188356 KB	Output is correct
15	Correct	466 ms	188520 KB	Output is correct
16	Correct	462 ms	188376 KB	Output is correct
17	Correct	340 ms	188408 KB	Output is correct
18	Correct	329 ms	188300 KB	Output is correct
19	Correct	452 ms	188508 KB	Output is correct
20	Correct	462 ms	188484 KB	Output is correct