Submission #228810

#	Time	Username	Problem	Language	Result	Execution time	Memory
228810		Haunted_Cpp	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	379 ms	104828 KiB

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_left;
	bool lazy_right;
	Node () {
		l = r = nullptr;
		sum = 0;
		lazy_left = lazy_right = false;
	}
};
 
Node *root;

void push_left (Node *&cur, int lo, int hi) {
	if (!cur -> lazy_left) return;
	int mid = lo + (hi - lo) / 2;
	if (lo != hi) {
		if (cur -> l == nullptr) cur -> l = new Node;
		cur -> l -> sum = mid - lo + 1;
		cur -> l -> lazy_left = true;
		cur -> l -> lazy_right = true;
	}
	cur -> lazy_left = false;
}

void push_right (Node *&cur, int lo, int hi) {
	if (!cur -> lazy_right) return;
	int mid = lo + (hi - lo) / 2;
	if (lo != hi) {
		if (cur -> r == nullptr) cur -> r = new Node;
		cur -> r -> sum = hi - mid;
		cur -> r -> lazy_left = true;
		cur -> r -> lazy_right = true;
	}
	cur -> lazy_right = false;
}
	
int range_query (Node *&cur, int ql, int qr, int lo, int hi) {
	if (!cur || lo > qr || hi < ql) return 0;
	if (lo >= ql && hi <= qr) {
		return cur -> sum;
	}
	int mid = lo + (hi - lo) / 2;
	int res = 0;
	if (mid >= ql) {
		push_left (cur, lo, hi);
		res += range_query (cur -> l, ql, qr, lo, mid);
	}
	if (mid + 1 <= qr) {
		push_right (cur, lo, hi);
		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 -> sum = hi - lo + 1;
		cur -> lazy_left = cur -> lazy_right = true;
		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);
	}
	push_left (cur, lo, hi); 
	push_right (cur, lo, 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 / 100