Submission #228805

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
228805	2020-05-02T16:14:53 Z	Haunted_Cpp	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	539 ms	187296 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;
	Node () {
		l = r = nullptr;
		sum = 0;
		lazy = false;
	}
};
 
Node *root;

void push (Node *cur, int lo, int hi) {
	cur -> sum = hi - lo + 1;
	if (lo != hi) {
		if (cur -> l == nullptr) cur -> l = new Node;
		cur -> l -> lazy = true;
		if (cur -> r == nullptr) cur -> r = new Node;
		cur -> r -> lazy = true;
	}
	cur -> lazy = false;
}
	
int range_query (Node *cur, int ql, int qr, int lo, int hi) {
	if (!cur || lo > qr || hi < ql) return 0;
	if (cur -> lazy) push (cur, lo, hi);
	if (lo >= ql && hi <= qr) return cur -> sum;
	int mid = lo + (hi - lo) / 2;
	int res = 0;
	if (mid >= ql) {
		res += range_query (cur -> l, ql, qr, lo, mid);
	}
	if (mid + 1 <= qr) {
		res += range_query (cur -> r, ql, qr, mid + 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 -> lazy = true;
	//	push (cur, lo, hi);
		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);
	}
	if (cur -> l && cur -> l -> lazy) push (cur -> l, lo, mid);
	if (cur -> r && cur -> r -> lazy) push (cur -> r, mid + 1, 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	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	23 ms	4472 KB	Output is correct
5	Correct	24 ms	5376 KB	Output is correct
6	Correct	22 ms	5248 KB	Output is correct
7	Correct	23 ms	5376 KB	Output is correct
8	Correct	159 ms	39480 KB	Output is correct
9	Correct	330 ms	67960 KB	Output is correct
10	Correct	344 ms	75384 KB	Output is correct
11	Correct	359 ms	81144 KB	Output is correct
12	Correct	363 ms	83664 KB	Output is correct
13	Correct	324 ms	98552 KB	Output is correct
14	Correct	332 ms	99320 KB	Output is correct
15	Correct	537 ms	181620 KB	Output is correct
16	Correct	534 ms	183088 KB	Output is correct
17	Correct	332 ms	102648 KB	Output is correct
18	Correct	335 ms	102648 KB	Output is correct
19	Correct	535 ms	187000 KB	Output is correct
20	Correct	539 ms	187296 KB	Output is correct