Submission #228804

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
228804	2020-05-02T16:14:15 Z	Haunted_Cpp	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	539 ms	187128 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	4 ms	384 KB	Output is correct
4	Correct	20 ms	4480 KB	Output is correct
5	Correct	22 ms	5376 KB	Output is correct
6	Correct	23 ms	5248 KB	Output is correct
7	Correct	23 ms	5376 KB	Output is correct
8	Correct	163 ms	39416 KB	Output is correct
9	Correct	339 ms	67952 KB	Output is correct
10	Correct	333 ms	75384 KB	Output is correct
11	Correct	352 ms	81144 KB	Output is correct
12	Correct	358 ms	83620 KB	Output is correct
13	Correct	306 ms	98552 KB	Output is correct
14	Correct	315 ms	99320 KB	Output is correct
15	Correct	508 ms	181496 KB	Output is correct
16	Correct	506 ms	183160 KB	Output is correct
17	Correct	327 ms	102776 KB	Output is correct
18	Correct	323 ms	102760 KB	Output is correct
19	Correct	525 ms	187000 KB	Output is correct
20	Correct	539 ms	187128 KB	Output is correct