제출 #969373

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

apple

#include<bits/stdc++.h>
#define ll int
#define md (r+l)/2
using namespace std;
ll m,i,x,y,d,c,ans,mid;
struct node{
	node *le,*ri;
	ll val,lazy,l,r;
	void create(ll x,ll y){
		val=0;
		lazy=0;
		l=x;
		r=y;
		if(l==r) return;
		le=NULL;
		ri=NULL;
	}
	void fix(){          
		if(le==NULL){
			le=new node;
			le->create(l,md);
		}
		if(ri==NULL){
			ri=new node;
			ri->create(md+1,r);
		}
		if(lazy==0) return;
		le->val=le->r-le->l+1;
		ri->val=ri->r-ri->l+1;
		le->lazy=lazy;
		ri->lazy=lazy;
		lazy=0;
	}
	ll query(ll x,ll y){
		if(l>y || r<x) return 0;
		if(l>=x && r<=y) return val;
		fix();
		return le->query(x,y)+ri->query(x,y);
	}
	void update(ll x,ll y){
		if(l>y || r<x) return;
		if(l>=x && r<=y){
			val=r-l+1;
			lazy=1;
			return;
		}
		fix();
		le->update(x,y);
		ri->update(x,y);
		val=le->val+ri->val;
	}
} s;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> m;
	s.create(1,1e9);
	for(i=1;i<=m;i++){
		cin >> d >> x >> y;
		if(d==1){
			ans=s.query(x+c,y+c);
			cout << ans << "\n";
			c=ans;
		}
		else{
			s.update(x+c,y+c);
		}
	}
}

• Subtask 1: 100 / 100