oj.uz

Submission #638870

# Submission time Handle Problem Language Result Execution time Memory
638870 2022-09-07T18:35:17 Z MohamedAhmed04 Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 260 ms 71252 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 2004 KB Output is correct
5 Correct 10 ms 2388 KB Output is correct
6 Correct 13 ms 2312 KB Output is correct
7 Correct 10 ms 2384 KB Output is correct
8 Correct 74 ms 15708 KB Output is correct
9 Correct 168 ms 27424 KB Output is correct
10 Correct 203 ms 30104 KB Output is correct
11 Correct 182 ms 32288 KB Output is correct
12 Correct 181 ms 33084 KB Output is correct
13 Correct 163 ms 38620 KB Output is correct
14 Correct 151 ms 38908 KB Output is correct
15 Correct 252 ms 69272 KB Output is correct
16 Correct 245 ms 69680 KB Output is correct
17 Correct 150 ms 40236 KB Output is correct
18 Correct 161 ms 40140 KB Output is correct
19 Correct 260 ms 71172 KB Output is correct
20 Correct 256 ms 71252 KB Output is correct