제출 #638872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638872		MohamedAhmed04	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	232 ms	69044 KiB

apple

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

int arr[MAX] ;
int q ;

int tree[MAX * 30] , lazy[MAX * 30] ;
int lft[MAX * 30] , rht[MAX * 30] ;

int id = 1 ;

int Left(int node)
{
	if(!lft[node])
		lft[node] = ++id ;
	return lft[node] ;
}

int Right(int node)
{
	if(!rht[node])
		rht[node] = ++id ;
	return rht[node] ;
}

void update(int node , int l , int r , int from , int to , bool flag)
{
	if(from > r || to < l)
		return ;
	flag |= lazy[node] ;
	if(l >= from && r <= to)
	{
		tree[node] = r-l+1 , lazy[node] = 1 ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(Left(node) , l , mid , from , to , flag) ;
	update(Right(node) , mid+1 , r , from , to , flag) ;
	tree[node] = tree[Left(node)] + tree[Right(node)] ;
	if(flag)
		tree[node] = r-l+1 ;
}

int query(int node , int l , int r , int from , int to , bool flag)
{
	if(from > r || to < l)
		return 0 ;
	flag |= lazy[node] ;
	if(l >= from && r <= to)
	{
		if(flag)
			return (r-l+1) ;
		else
			return tree[node] ;
	}
	int mid = (l + r) >> 1 ;
	int x = query(Left(node) , l , mid , from , to , flag) ;
	int y = query(Right(node) , mid+1 , r , from , to , flag) ;
	return (x + y) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>q ;
	int cnt = 0 ;
	while(q--)
	{
		int ty , l , r ;
		cin>>ty>>l>>r ;
		l += cnt , r += cnt ;
		if(ty == 1)
		{
			int ans = query(1 , 1 , 1e9 , l , r , 0) ;
			cnt = ans ;
			cout<<ans<<"\n" ;
		}
		else
			update(1 , 1 , 1e9 , l , r , 0) ;
	}
	return 0 ;
}		

• Subtask 1: 100 / 100