Submission #439357

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
439357	2021-06-29T17:20:46 Z	pauloamed	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	508 ms	186388 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) {
  	push_lazy(node);
  	if (l == segtree[node].tl && r == segtree[node].tr) {
  		segtree[node].lazy = segtree[node].tr - segtree[node].tl + 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 = 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);
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	185836 KB	Output is correct
2	Correct	81 ms	185800 KB	Output is correct
3	Correct	81 ms	185832 KB	Output is correct
4	Correct	100 ms	185816 KB	Output is correct
5	Correct	95 ms	185876 KB	Output is correct
6	Correct	99 ms	185764 KB	Output is correct
7	Correct	101 ms	185832 KB	Output is correct
8	Correct	221 ms	185968 KB	Output is correct
9	Correct	413 ms	186236 KB	Output is correct
10	Correct	440 ms	186188 KB	Output is correct
11	Correct	394 ms	186128 KB	Output is correct
12	Correct	398 ms	186116 KB	Output is correct
13	Correct	344 ms	186308 KB	Output is correct
14	Correct	354 ms	186332 KB	Output is correct
15	Correct	507 ms	186348 KB	Output is correct
16	Correct	489 ms	186324 KB	Output is correct
17	Correct	367 ms	186308 KB	Output is correct
18	Correct	372 ms	186388 KB	Output is correct
19	Correct	508 ms	186312 KB	Output is correct
20	Correct	507 ms	186240 KB	Output is correct