Submission #93465

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93465	2019-01-08T14:48:54 Z	Aydarov03	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	571 ms	157536 KB

apple

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
vector <int> ans;

struct st
{
		int l , r , val;
		bool add;
		st()
		{
			l = r = val = add = 0;
		}
}tree[N * 100];

int cnt = 1;

void push( int v , int tl , int tr )
{
		if(tl != tr)
		{			
			if( !tree[v].l )tree[v].l = ++cnt;
			if( !tree[v].r )tree[v].r = ++cnt;
		}
		if( !tree[v].add )return;
		
		tree[v].val = tr - tl + 1;
	
		if( tl != tr )
		tree[ tree[v].l ].add = tree[ tree[v].r ].add = 1;
}

void upd( int l , int r , int v = 1 , int tl = 1 , int tr = 1e9 )
{
		push( v , tl , tr );
		if( tl > r || l > tr )return;
		
		if(l <= tl && tr <= r)
		{
				tree[v].add = 1;
				push( v , tl , tr );
				return;
		}		
		int tm = (tl + tr) >> 1;
		
		upd( l , r , tree[v].l , tl , tm );
		upd( l , r , tree[v].r , tm+1 , tr );
		tree[v].val = tree[tree[v].l].val + tree[tree[v].r].val;
		
}


int get( int l , int r , int v = 1 , int tl = 1 , int tr = 1e9)
{
	push( v , tl , tr );
	
	if( tl > r || tr < l )
		return 0;
	if( l <= tl && tr <= r )
	{
				return tree[v].val;
	}
	
	
	int tm = (tl + tr) >> 1;
	
	return get( l , r , tree[v].l , tl , tm ) + get( l , r , tree[v].r , tm+1 , tr );
}



main()
{
	int t , c = 0;
	cin >> t;
	
	while( t-- )
	{
		int tp , l , r;		
		scanf("%d%d%d" , &tp , &l , &r );
		
		l += c , r += c;
		
		if( tp == 1 )
		{
		 cout << ( c = get( l , r ) ) << endl;
		}
		
		if( tp == 2 )
			upd(l , r);
	}
	
	
}

Compilation message

apple.cpp:72:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
apple.cpp: In function 'int main()':
apple.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &tp , &l , &r );
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	156940 KB	Output is correct
2	Correct	125 ms	157012 KB	Output is correct
3	Correct	126 ms	156920 KB	Output is correct
4	Correct	145 ms	156920 KB	Output is correct
5	Correct	148 ms	156984 KB	Output is correct
6	Correct	145 ms	156908 KB	Output is correct
7	Correct	144 ms	156936 KB	Output is correct
8	Correct	273 ms	157108 KB	Output is correct
9	Correct	466 ms	157368 KB	Output is correct
10	Correct	471 ms	157432 KB	Output is correct
11	Correct	523 ms	157300 KB	Output is correct
12	Correct	464 ms	157428 KB	Output is correct
13	Correct	412 ms	157432 KB	Output is correct
14	Correct	437 ms	157432 KB	Output is correct
15	Correct	571 ms	157536 KB	Output is correct
16	Correct	489 ms	157452 KB	Output is correct
17	Correct	428 ms	157436 KB	Output is correct
18	Correct	435 ms	157432 KB	Output is correct
19	Correct	522 ms	157444 KB	Output is correct
20	Correct	552 ms	157380 KB	Output is correct