Submission #439366

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
439366	2021-06-29T17:26:36 Z	pauloamed	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	528 ms	186464 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{
  static const int LAZY_NEUTRAL = -1;
  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(LAZY_NEUTRAL), l(-1), r(-1) {}
  };

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


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

  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 = -1;
    segtree[1].tl = 1; segtree[1].tr = 1e9;
    // LAZY_NEUTRAL = -1;
  }

  void push_lazy(int node) {
  	if (segtree[node].lazy != LAZY_NEUTRAL) {
  		segtree[node].val = segtree[node].lazy;
      maybeCreateChilds(node);
  		segtree[segtree[node].l].lazy = segtree[segtree[node].l].tr - segtree[segtree[node].l].tl + 1;
      segtree[segtree[node].r].lazy = segtree[segtree[node].r].tr - segtree[segtree[node].r].tl + 1;
  		segtree[node].lazy = LAZY_NEUTRAL;
  	}
  }

  void update(int node, int l, int r, int value) {
  	push_lazy(node);
  	if (l == segtree[node].tl && r == segtree[node].tr) {
  		segtree[node].lazy = (segtree[node].tr - segtree[node].tl + 1) * value;
  		push_lazy(node);
  	} else {
      maybeCreateChilds(node);

      int mid = (segtree[node].tl + segtree[node].tr) / 2;    
  		if (l > mid) update(segtree[node].r, l, r, value);
  		else if (r <= mid) update(segtree[node].l, l, r, value);
  		else {
  			update(segtree[node].l, l, mid, value);
  			update(segtree[node].r, mid + 1, r, value);
  		}

  		push_lazy(segtree[node].l);
  		push_lazy(segtree[node].r);
  		segtree[node].val = merge(
        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 merge(
        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, 1);
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	185800 KB	Output is correct
2	Correct	83 ms	185776 KB	Output is correct
3	Correct	80 ms	185844 KB	Output is correct
4	Correct	107 ms	185796 KB	Output is correct
5	Correct	103 ms	185876 KB	Output is correct
6	Correct	95 ms	185812 KB	Output is correct
7	Correct	98 ms	185792 KB	Output is correct
8	Correct	220 ms	186100 KB	Output is correct
9	Correct	399 ms	186308 KB	Output is correct
10	Correct	391 ms	186256 KB	Output is correct
11	Correct	422 ms	186180 KB	Output is correct
12	Correct	433 ms	186204 KB	Output is correct
13	Correct	362 ms	186312 KB	Output is correct
14	Correct	342 ms	186204 KB	Output is correct
15	Correct	494 ms	186424 KB	Output is correct
16	Correct	515 ms	186216 KB	Output is correct
17	Correct	363 ms	186464 KB	Output is correct
18	Correct	355 ms	186416 KB	Output is correct
19	Correct	499 ms	186308 KB	Output is correct
20	Correct	528 ms	186304 KB	Output is correct