제출 #339080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339080		amunduzbaev	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	531 ms	138988 KiB

apple

/** made by amunduzbaev **/
#include <bits/stdc++.h>

using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

const int N = 1e9+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int s, n, m, k, ans, cur;

struct node{
	int sum, lz;
	node *lx, *rx;
	
	node(){
		sum = 0, lz = 0;
		lx = NULL;
		rx = NULL;
	}
	
};

void prop(node *x, int len){
	if(x->lz){
		if(x->lx != NULL) x->lx->lz = 1;
		if(x->rx != NULL) x->rx->lz = 1;
		x->sum = len;
	}
}

void update(node *x, int l, int r, int lx, int rx){
	int m = (lx + rx)/2;
	prop(x, rx - lx +1);
	
	if(lx > r || rx < l) return;
	if(lx >= l && rx <= r){
		x->lz = 1;
		prop(x, rx-lx+1);
		return;
	}
	if(x->lx == NULL) x->lx = new node();
	if(x->rx == NULL) x->rx = new node();
	
	prop(x, rx - lx +1);
	update(x->lx, l, r, lx, m);
	update(x->rx, l, r, m+1, rx);
	x->sum = x->lx->sum + x->rx->sum;
}

int qq(node *x, int l, int r, int lx, int rx){
	int m = (lx + rx)/2;
	prop(x, rx - lx+1);
	
	if(lx > r || rx < l) return 0;
	if(lx >= l && rx <= r) return x->sum;
	
	if(x->lx == NULL) x->lx = new node();
	if(x->rx == NULL) x->rx = new node();
	prop(x, rx - lx +1);
	
	int res = qq(x->lx, l, r, lx, m);
	res += qq(x->rx, l, r, m+1, rx);
	x->sum = x->lx->sum + x->rx->sum;
	return res;
}

void solve(){
	fastios
	cin>>m;
	int c = 0;
	node *root = new node();
	for(int i=0;i<m;i++){
		int t;
		cin>>t;
		if(t == 1){
			int l, r;
			cin>>l>>r;
			c = qq(root, l+c, r+c, 1, N);
			cout<< c <<"\n";
		}else{
			int l, r;
			cin>>l>>r;
			update(root, l+c, r+c, 1, N);
		}
	}
	return;
}

int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

• Subtask 1: 100 / 100