Submission #538771

#TimeUsernameProblemLanguageResultExecution timeMemory
538771xuliuMonkey and Apple-trees (IZhO12_apple)C++17
100 / 100
428 ms207652 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int mod = 1e9 + 7;
const ll infL = 1e18 + 7;
const int inf = 1e9 + 7;

struct node {
	int l, r;
	ll sum = 0, lazy = -1;
	node *left = nullptr, *right = nullptr;
	node(int lb, int rb) {
		l = lb;
		r = rb;
	}
	void extend() {
		if(!left && l != r) {
			int t = (l+r)/2;
			left = new node(l, t);
			right = new node(t+1, r);
		}
	}
	void push() {
		if(lazy != -1) {
			extend();
			left->lazy = lazy;
			right->lazy = lazy;
			int m = (l+r)/2;
			left->sum = m-l+1;
			right->sum = r-(m+1)+1;
			lazy = -1;
		}
	}
	void set(int lx, int rx) {
		if(lx <= l && rx >= r) {
			sum = r-l+1;
			lazy = 1;
			return;
		}
		if(lx > r || rx < l) return;
		push();
		extend();
		left->set(lx, rx); right->set(lx, rx);
		sum = left->sum + right->sum;
	}
	ll get(int lx, int rx) {
		if(lx <= l && rx >= r) return sum;
		if(lx > r || rx < l) return 0;
		push();
		extend();
		return left->get(lx, rx) + right->get(lx, rx);
	}
};

const int N = 1e9 + 4;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int m, c = 0; cin>>m;
	node root(0, N);
	for(int i=0; i<m; i++) {
		int d, x, y; cin>>d>>x>>y;
		x += c; y += c;
		if(d == 1) {
			c = root.get(x, y);
			cout<<c<<"\n";
		}
		else {
			root.set(x, y);
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...