Submission #228794

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
228794	2020-05-02T15:15:53 Z	Haunted_Cpp	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	872 ms	260384 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 expandir (Node *&cur) {
	if (cur == nullptr) cur = new Node;
	cur -> lazy = true;
}
 
void push (Node *&cur, int lo, int hi) {
	cur -> sum = hi - lo + 1;
	if (lo != hi) {
		expandir (cur -> l);
		expandir (cur -> r);
	}
	cur -> lazy = false;
}
	
int range_query (Node *&cur, int ql, int qr, int lo, int hi) {
	if (cur == nullptr) return 0;
	if (cur -> lazy) push (cur, lo, hi);
	if (lo > qr || hi < ql) return 0;
	if (lo >= ql && hi <= qr) return cur -> sum;
	int mid = lo + (hi - lo) / 2;
	return range_query (cur -> l, ql, qr, lo, mid)
	+ range_query (cur -> r, ql, qr, mid + 1, hi);
}
 
void range_set (Node *&cur, int ql, int qr, int lo, int hi) {
	if (lo > qr || hi < ql) {
		if (cur == nullptr) return;
		if (cur -> lazy) push (cur, lo, hi);
		return;
	}
	if (cur == nullptr) cur = new Node ();
	if (cur -> lazy) push (cur, lo, hi);
	if (lo >= ql && hi <= qr) {
		cur -> lazy = true;
		push (cur, lo, hi);
		return;
	}
	int mid = lo + (hi - lo) / 2;
	range_set (cur -> l, ql, qr, lo, mid);
	range_set (cur -> r, ql, qr, mid + 1, hi);
	cur -> sum = (cur -> l ? cur -> l -> sum : 0) + (cur -> r ? cur -> r -> sum : 0);
}	

void del (Node *cur, int l, int r) {
	if (cur == nullptr) return;
	int mid = l + (r - l) / 2;
	del (cur -> l, l, mid);
	del (cur -> r, mid + 1, r);
	delete (cur);
}
 
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);
		}
	}
	del (root, 0, N);
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	28 ms	5888 KB	Output is correct
5	Correct	32 ms	7032 KB	Output is correct
6	Correct	32 ms	6904 KB	Output is correct
7	Correct	32 ms	7040 KB	Output is correct
8	Correct	225 ms	51576 KB	Output is correct
9	Correct	453 ms	87548 KB	Output is correct
10	Correct	489 ms	98200 KB	Output is correct
11	Correct	507 ms	106544 KB	Output is correct
12	Correct	520 ms	110224 KB	Output is correct
13	Correct	504 ms	137208 KB	Output is correct
14	Correct	521 ms	138364 KB	Output is correct
15	Correct	840 ms	252664 KB	Output is correct
16	Correct	860 ms	254584 KB	Output is correct
17	Correct	525 ms	143284 KB	Output is correct
18	Correct	530 ms	143352 KB	Output is correct
19	Correct	872 ms	260384 KB	Output is correct
20	Correct	841 ms	260344 KB	Output is correct