Submission #228815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
228815	2020-05-02T16:54:12 Z	Haunted_Cpp	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	373 ms	104824 KB

apple

#include <iostream>
#include <vector>
#include <cstring>
#include <cassert>
#include <bitset>
#include <iomanip>
#include <algorithm>
 
#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
const int N = 1e9;
 
struct Node {
	Node *l, *r; 
	int sum;
	bool lazy_left;
	bool lazy_right;
	Node () {
		l = r = nullptr;
		sum = 0;
		lazy_left = lazy_right = false;
	}
};
 
Node *root;

void push_left (Node *cur, int lo, int hi) {
	if (!cur -> lazy_left) return;
	if (lo != hi) {
		if (cur -> l == nullptr) cur -> l = new Node;
		cur -> l -> sum = (lo + (hi - lo) / 2) - lo + 1;
		cur -> l -> lazy_left = true;
		cur -> l -> lazy_right = true;
	}
	cur -> lazy_left = false;
}

void push_right (Node *cur, int lo, int hi) {
	if (!cur -> lazy_right) return;
	if (lo != hi) {
		if (cur -> r == nullptr) cur -> r = new Node;
		cur -> r -> sum = hi - (lo + (hi - lo) / 2);
		cur -> r -> lazy_left = true;
		cur -> r -> lazy_right = true;
	}
	cur -> lazy_right = false;
}
	
int range_query (Node *cur, int ql, int qr, int lo, int hi) {
	if (!cur || lo > qr || hi < ql) return 0;
	if (lo >= ql && hi <= qr) return cur -> sum;
	int res = 0;
	if (lo + (hi - lo) / 2 >= ql) {
		push_left (cur, lo, hi);
		res += range_query (cur -> l, ql, qr, lo, lo + (hi - lo) / 2);
	}
	if (lo + (hi - lo) / 2 + 1 <= qr) {
		push_right (cur, lo, hi);
		res += range_query (cur -> r, ql, qr, lo + (hi - lo) / 2 + 1, hi);
	}
	return res;
}
 
void range_set (Node *cur, int ql, int qr, int lo, int hi) {
	if (lo > qr || hi < ql) return;
	if (lo >= ql && hi <= qr) {
		cur -> sum = hi - lo + 1;
		cur -> lazy_left = cur -> lazy_right = true;
		return;
	}
	int mid = lo + (hi - lo) / 2;
	if (mid >= ql) {
		if (cur -> l == nullptr) cur -> l = new Node;
		range_set (cur -> l, ql, qr, lo, mid);
	}
	if (mid + 1 <= qr) {
		if (cur -> r == nullptr) cur -> r = new Node;
		range_set (cur -> r, ql, qr, mid + 1, hi);
	}
	push_left (cur, lo, hi); 
	push_right (cur, lo, hi);
	cur -> sum = (cur -> l ? cur -> l -> sum : 0) + (cur -> r ? cur -> r -> sum : 0);
}	
 
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	root = new Node ();
	int q;
	cin >> q;
	int C = 0;
	while (q--) {
		int task, lo, hi;
		cin >> task >> lo >> hi;
		--lo; --hi;
		lo += C;
		hi += C;
		if (task == 1) {
			// Range Query, update C
			C = range_query (root, lo, hi, 0, N);
			cout << C << '\n';
		} else {
			// Range Set
			range_set (root, lo, hi, 0, N);
		}
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	16 ms	2816 KB	Output is correct
5	Correct	23 ms	3328 KB	Output is correct
6	Correct	19 ms	3328 KB	Output is correct
7	Correct	23 ms	3328 KB	Output is correct
8	Correct	152 ms	23052 KB	Output is correct
9	Correct	270 ms	39776 KB	Output is correct
10	Correct	264 ms	43896 KB	Output is correct
11	Correct	265 ms	47188 KB	Output is correct
12	Correct	287 ms	48376 KB	Output is correct
13	Correct	237 ms	55392 KB	Output is correct
14	Correct	238 ms	55928 KB	Output is correct
15	Correct	358 ms	101752 KB	Output is correct
16	Correct	369 ms	102572 KB	Output is correct
17	Correct	237 ms	57720 KB	Output is correct
18	Correct	226 ms	57592 KB	Output is correct
19	Correct	368 ms	104824 KB	Output is correct
20	Correct	373 ms	104824 KB	Output is correct