제출 #1276271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276271		WH8	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	485 ms	205664 KiB

apple

#include <bits/stdc++.h>
using namespace std;

#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second

struct node{
	int s,e,m,lz,v;
	node *l=nullptr, *r=nullptr;
	node (int S,int E){
		s=S,e=E,m=(s+e)/2,lz=-1,v=0; // lz is rangeset, v is sum. 
	}
	void prop(){
		if(s!=e and l == nullptr){
			l=new node(s, m);
			r = new node(m+1, e);
		}
		if(s==e or lz==-1)return;

		l->v=lz*(m-s+1), r->v=lz*(e-m), r->lz =lz, l->lz =lz;
		lz=-1;
	}
	void rangeset(int S,int E, int V){
		//~ printf("%lld to %lld, v %lld\n", s,e,v);
		if(S<=s and e<=E){
			v=(e-s+1)*V;
			lz=V;
			return;
		}
		prop();
		if(E <= m)l->rangeset(S, E, V);
		else if(S > m)r->rangeset(S, E, V);
		else l->rangeset(S,m, V), r->rangeset(m+1, E, V);
		v=l->v+r->v;
	}
	int rangeadd(int S, int E){
		if(S<=s and e<=E){
			return v;
		}
		prop();
		if(E <= m)return l->rangeadd(S, E);
		else if(S>m)return r->rangeadd(S,E);
		return l->rangeadd(S, m)+ r->rangeadd(m+1, E);
	}
} *root;
	
signed main(){
	int n;cin>>n;
	root =new node(0, 1e9+5);
	int c=0;
	for(int i=0;i<n;i++){
		int t,a,b;cin>>t>>a>>b;
		if(t==2){
			root->rangeset(a+c,b+c,1);
		}
		else {
			int res=root->rangeadd(a+c,b+c);
			c=res;
			cout<<res<<"\n";
		}
	}
}		

• Subtask 1: 100 / 100