Submission #989687

#	Time	Username	Problem	Language	Result	Execution time	Memory
989687		Drifter24	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	348 KiB

apple

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// struct Node {
// 	int sum, lazy, tl, tr, l, r;
// 	Node() : sum(0), lazy(0), l(-1), r(-1) {}
// };

// // [1,1e9] - indexed 1
// struct SegTree {
// 	vector<Node> st;
// 	int cnt = 2;

// 	void build(int n) {
// 		st.assign(64*123456, Node());
// 		st[1].sum = 0;
// 		st[1].lazy = 0;
// 		st[1].tl = 1;
// 		st[1].tr = n;
// 	}

// 	void push_left(int node){
// 		if (st[node].l == -1) {
// 			st[node].l = cnt++;
// 			st[st[node].l].tl = st[node].tl;
// 			st[st[node].l].tr = (st[node].tl + st[node].tr) / 2;
// 		}
// 	}

// 	void push_right(int node){
// 		if (st[node].r == -1) {
// 			st[node].r = cnt++;
// 			st[st[node].r].tl = (st[node].tl + st[node].tr) / 2 + 1;
// 			st[st[node].r].tr = st[node].tr;
// 		}
// 	}

// 	void push_lazy(int node) {
// 		if (st[node].lazy) {
// 			st[node].sum = st[node].tr - st[node].tl + 1;
// 			push_left(node);
// 			push_right(node);
// 			st[st[node].l].lazy = st[st[node].r].lazy = 1;
// 			st[node].lazy = 0;
// 		}
// 	}

// 	void update(int l, int r, int node=1) {
// 		push_lazy(node);
// 		if (l == st[node].tl && r == st[node].tr) {
// 			st[node].lazy = 1;
// 			push_lazy(node);
// 		} else {
// 			int mid = (st[node].tl + st[node].tr) / 2;
// 			push_left(node);
// 			push_right(node);

// 			if (l > mid) update(l, r,st[node].r);
// 			else if (r <= mid) update(l, r,st[node].l);
// 			else {
// 				update(l, mid, st[node].l);
// 				update(mid + 1, r, st[node].r);
// 			}

// 			push_lazy(st[node].l);
// 			push_lazy(st[node].r);
// 			st[node].sum = st[st[node].l].sum + st[st[node].r].sum;
// 		}
// 	}

// 	int get(int l, int r, int node=1) {
// 		push_lazy(node);
// 		if (l == st[node].tl && r == st[node].tr) return st[node].sum;
// 		int mid = (st[node].tl + st[node].tr) / 2;
// 		push_left(node);
// 		push_right(node);

// 		if (l > mid) return get(l, r, st[node].r);
// 		else if (r <= mid) return get(l, r, st[node].l);
// 		else return get(l, mid, st[node].l) + get(mid + 1, r, st[node].r);
// 	}
// };

struct node {
	int lz, lzL, lzR, val;
	node *L, *R;
	node(int lz = 0) : lz(lz), lzL(0), lzR(0), val(0), L(0), R(0) {}
	void propagate(int l, int r) {
		if(lz) {
			if(l != r) {
				if(L) L->lz = 1;
				else lzL = 1;
				if(R) R->lz = 1;
				else lzR = 1;
			}
			val = (r-l+1);
			lz = 0;
		}
	}
};
int get_val(node* root, int lz, int a, int b) {
	if(!root) return lz*(b-a+1);
	return root->val;
}
int null = 0;
struct SegTree { 
	node* root;
	int n; // 0-indexed
	SegTree(int n) : n(n), root(new node()) {}
	void update(int a, int b, int x) { update(root, a, b, 0, n-1, x); }
	void update(node* &root, int a, int b, int l, int r, int x, int lz = 0) {
		if((l > b || r < a) && !root) return;
		if(root == nullptr) root = new node(lz);
			root->propagate(l, r);
		if(l > b || r < a) return; 
		if(a <= l && r <= b) { 
			root->lz = x;
			root->propagate(l, r);
		} else {
			int m = (l+r) >> 1;
			update(root->L, a, b, l, m, x, root->lzL);
			update(root->R, a, b, m+1, r, x, root->lzR);
			root->val = get_val(root->L, root->lzL, l, m) + get_val(root->R, root->lzR, m+1, r);
		}
	}
	int get(int a, int b) { return get(root, a, b, 0, n-1); }
	int get(node* root, int a, int b, int l, int r, int lz = 0) {
		if(l > b || r < a) return null;
		if(root) root->propagate(l, r);
		if((a <= l && r <= b) || !root) { 
			return get_val(root, lz, l, r);
		} else {
			int m = (l+r) >> 1;
			return get(root->L, a, b, l, m, root->lzL) + get(root->R, a, b, m+1, r, root->lzR);
		}
	}
};


int main() {
	iostream::sync_with_stdio(false);cin.tie(nullptr);
	int q;cin>>q;
	int op,l,r,c=0;
	SegTree st(1e9);
	while(q--){
		cin>>op>>l>>r;
		l--;r--;
		if(op==1){
			c=st.get(l+c,r+c);
			cout<<c<<"\n";
		}else{
			st.update(l+c,r+c,1);
		}
	}
	return 0;
}

Compilation message (stderr)

apple.cpp: In constructor 'SegTree::SegTree(int)':
apple.cpp:109:6: warning: 'SegTree::n' will be initialized after [-Wreorder]
  109 |  int n; // 0-indexed
      |      ^
apple.cpp:108:8: warning:   'node* SegTree::root' [-Wreorder]
  108 |  node* root;
      |        ^~~~
apple.cpp:110:2: warning:   when initialized here [-Wreorder]
  110 |  SegTree(int n) : n(n), root(new node()) {}
      |  ^~~~~~~

• Subtask 1: 0 / 100