제출 #1257227

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

apple

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 100005
#define N 1e9

struct Node{
	Node *left,*right;
	int val;
	
	Node(){
		val=0;
		left=NULL;
		right=NULL;
	}
};

inline bool check(int l1,int r1,int l2,int r2){
	int ll=max(l1,l2);
	int rr=min(r1,r2);
	return ll<=rr;
}

inline int ara(int l1,int r1,int l2,int r2){
	int ll=max(l1,l2);
	int rr=min(r1,r2);
	return rr-ll+1;
}

inline void update(Node *node,int start,int end,int l,int r,int val){
	if(node==NULL || start>end || start>r || end<l)return ;
	//cout<<node->val<<" "<<l<<" "<<r<<" "<<start<<" "<<end<<endl;
	if(start>=l && end<=r){
		node->val=end-start+1;
		return ;
	}
	if(check(l,r,start,mid)){
		if(node->left==NULL){
			node->left=new Node();
			if(node->val==end-start+1)node->left->val=mid-start+1;
		}
		update(node->left,start,mid,l,r,val);
	}
	if(check(l,r,mid+1,end)){
		if(node->right==NULL){
			node->right=new Node();
			if(node->val==end-start+1)node->right->val=end-(mid+1)+1;
		}
		update(node->right,mid+1,end,l,r,val);
	}
	if(node->val==end-start+1)return;
	node->val=0;
	if(node->left!=NULL)node->val+=node->left->val;
	if(node->right!=NULL)node->val+=node->right->val;
	//cout<<node->val<<" "<<start<<" "<<end<<" "<<l<<" "<<r<<endl;
}

inline int query(Node *node,int start,int end,int l,int r){
	if(node==NULL || start>end || start>r || end<l)return 0;
	//cout<<node->val<<" "<<start<<" "<<end<<" "<<l<<" "<<r<<endl;
	if(node->val==end-start+1){
		return ara(start,end,l,r);
	}
	if(start>=l && end<=r){
		return node->val;
	}
	return query(node->left,start,mid,l,r)+query(node->right,mid+1,end,l,r);
}

int32_t main(){
	faster
	int q;cin>>q;
	int c=0;
	Node *root=new Node();
	while(q--){
		int ty;cin>>ty;
		int l,r;cin>>l>>r;
		l+=c;
		r+=c;
		if(ty==1){
			int cev=query(root,1,N,l,r);
			cout<<cev<<'\n';
			c=cev;
		}
		else{
			update(root,1,N,l,r,1);
		}
	}
	return 0;	
}

• Subtask 1: 100 / 100