제출 #909716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
909716		dsyz	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	246 ms	164720 KiB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (1000005)
struct node{
	ll s,e,m,v;
	bool lazy;
	node *l = nullptr, *r = nullptr;
	node(ll S,ll E){
		s = S;
		e = E;
		m = (s + e) / 2;
		v = 0;
		lazy = 0;
	}
	void create(){
		if(l == nullptr && s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propo(){
		create();
		if(lazy == 0) return;
		v = lazy * (e - s + 1);
		if(s != e){
			l->lazy = lazy;
			r->lazy = lazy;
		}
		lazy = 0;
	}
	void update(ll x,ll y,ll nval){
		if(v == e - s + 1) return;
		propo();
		if(s == x && e == y){
			lazy = nval;
			return;
		}else{
			if(x > m) r -> update(x,y,nval);
			else if(y <= m) l -> update(x,y,nval);
			else l -> update(x,m,nval), r -> update(m + 1,y,nval);
			l->propo(), r->propo();
			v = l->v + r->v;
		}
	}
	ll query(ll x,ll y){
		propo();
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r->query(x,y);
			else if(y <= m) return l->query(x,y);
			else return l->query(x,m) + r-> query(m + 1,y);
		}
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll M;
	cin>>M;
	root = new node(0,1e9 + 5);
	ll D, X, Y, C = 0;
	while(M--){
		cin>>D>>X>>Y;
		X += C, Y += C;
		if(D == 1){ //query
			C = root -> query(X,Y);
			cout<<C<<'\n';
		}else if(D == 2){ //update
			root -> update(X,Y,1);
		}
	}
}

• Subtask 1: 100 / 100