Submission #380933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
380933	2021-03-23T17:42:15 Z	wind_reaper	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	502 ms	188640 KB

apple

#include <bits/stdc++.h>

using namespace std;

struct SegmentTree{
	struct Node{
		Node *lc, *rc;
		int val, lazy;

		Node() : lc(0), rc(0) {
			val = 0;
			lazy = 0;
		}
	};

	deque<Node> tree;
	Node* new_node(){
		tree.emplace_back();
		return &tree.back();
	}

	Node *root;
	int L, R;
	SegmentTree(int _L, int _R){
		this->L = _L;
		this->R = _R;
		root = new_node();
	}

	void push(Node* &node, int l, int r){
		if(node->lazy == 0)
			return;
		node->val = r-l;
		if(!node->lc) node->lc = new_node();
		if(!node->rc) node->rc = new_node();
		node->lc->lazy = node->rc->lazy = 1;
		node->lazy = 0;
	}

	void upd(int l, int r, int val, Node* &node, int lx, int rx){
		if(!node) node = new_node();
		push(node, lx, rx);
		if(rx <= l || lx >= r)
			return;
		if(l <= lx && r >= rx){
			node->lazy = 1;
			push(node, lx, rx);
			return;
		}

		int mid = (lx + rx) >> 1;
		upd(l, r, val, node->lc, lx, mid);
		upd(l, r, val, node->rc, mid, rx);
		push(node->lc, lx, mid), push(node->rc, mid, rx);
		node->val = node->lc->val + node->rc->val;
	}

	int query(int l, int r, Node* &node, int lx, int rx){
		if(lx >= r || rx <= l || !node)
			return 0;
		push(node, lx, rx);
		if(l <= lx && r >= rx)
			return node->val;

		int mid = (lx + rx) >> 1;
		return query(l, r, node->lc, lx, mid) + query(l, r, node->rc, mid, rx);
	}

	void upd(int l, int r) { upd(l, r, 1, root, L, R); }

	int query(int l, int r) { return query(l, r, root, L, R); }
};

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int m;
	cin >> m;

	SegmentTree S(0, 1000000000);
	int c = 0;
	for(int i = 0; i < m; i++){
		int t, x, y;
		cin >> t >> x >> y;
		x += c, y += c;
		if(t == 1){
			cout << (c = S.query(x-1, y)) << '\n';
		}
		else{
			S.upd(x-1, y);
		}
	}
	return 0; 
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	16 ms	4588 KB	Output is correct
5	Correct	19 ms	5612 KB	Output is correct
6	Correct	20 ms	5356 KB	Output is correct
7	Correct	19 ms	5612 KB	Output is correct
8	Correct	155 ms	40816 KB	Output is correct
9	Correct	319 ms	71064 KB	Output is correct
10	Correct	330 ms	78228 KB	Output is correct
11	Correct	342 ms	84008 KB	Output is correct
12	Correct	345 ms	86548 KB	Output is correct
13	Correct	312 ms	99860 KB	Output is correct
14	Correct	312 ms	101268 KB	Output is correct
15	Correct	498 ms	183648 KB	Output is correct
16	Correct	491 ms	184928 KB	Output is correct
17	Correct	321 ms	104468 KB	Output is correct
18	Correct	317 ms	104596 KB	Output is correct
19	Correct	502 ms	188640 KB	Output is correct
20	Correct	497 ms	188556 KB	Output is correct