제출 #1188007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188007		elotelo966	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	304 ms	137292 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 500005

const int mod=1000000007;

int N=1000000000;

//int N=20;

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

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

• Subtask 1: 100 / 100