Submission #228791

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
228791	2020-05-02T14:59:38 Z	Haunted_Cpp	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	653 ms	260472 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, lazy;
	Node () {
		l = r = nullptr;
		sum = 0;
		lazy = 0;
	}
	Node (int delta) {
		l = r = nullptr;
		sum = 0;
		lazy = delta;
	}
};
 
Node *root;
 
void expandir (Node *&cur) {
	if (cur == nullptr) {
		cur = new Node (1);
	} else {
		cur -> lazy = 1;
	}
}
 
void push (Node *&cur, int lo, int hi) {
	cur -> sum = hi - lo + 1;
	if (lo != hi) {
		expandir (cur -> l);
		expandir (cur -> r);
	}
	cur -> lazy = 0;
}
	
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 (cur == nullptr) cur = new Node ();
	if (cur -> lazy) push (cur, lo, hi);
	if (lo > qr || hi < ql) return;
	if (lo >= ql && hi <= qr) {
		cur -> lazy = 1;
		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 -> sum + cur -> r -> sum;
}	
 
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	23 ms	5888 KB	Output is correct
5	Correct	27 ms	7032 KB	Output is correct
6	Correct	26 ms	6776 KB	Output is correct
7	Correct	27 ms	7032 KB	Output is correct
8	Correct	188 ms	51552 KB	Output is correct
9	Correct	371 ms	87544 KB	Output is correct
10	Correct	392 ms	98228 KB	Output is correct
11	Correct	421 ms	106488 KB	Output is correct
12	Correct	418 ms	110200 KB	Output is correct
13	Correct	392 ms	137208 KB	Output is correct
14	Correct	389 ms	138488 KB	Output is correct
15	Correct	646 ms	252536 KB	Output is correct
16	Correct	637 ms	254456 KB	Output is correct
17	Correct	417 ms	143352 KB	Output is correct
18	Correct	401 ms	143480 KB	Output is correct
19	Correct	653 ms	260344 KB	Output is correct
20	Correct	652 ms	260472 KB	Output is correct