Submission #228780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
228780	2020-05-02T14:36:57 Z	Haunted_Cpp	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	716 ms	262144 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 + 5;

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	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	24 ms	6016 KB	Output is correct
5	Correct	29 ms	7296 KB	Output is correct
6	Correct	28 ms	7032 KB	Output is correct
7	Correct	29 ms	7288 KB	Output is correct
8	Correct	220 ms	52540 KB	Output is correct
9	Correct	426 ms	89212 KB	Output is correct
10	Correct	433 ms	99960 KB	Output is correct
11	Correct	465 ms	108364 KB	Output is correct
12	Correct	472 ms	111992 KB	Output is correct
13	Correct	423 ms	139256 KB	Output is correct
14	Correct	437 ms	140408 KB	Output is correct
15	Correct	696 ms	254840 KB	Output is correct
16	Correct	700 ms	256760 KB	Output is correct
17	Correct	435 ms	145272 KB	Output is correct
18	Correct	429 ms	145528 KB	Output is correct
19	Correct	708 ms	262144 KB	Output is correct
20	Correct	716 ms	262144 KB	Output is correct