Submission #93460

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93460	2019-01-08T13:58:05 Z	Aydarov03	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	631 ms	263168 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 * 150];

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 || tree[v].val )return;
		
		tree[v].val = tr - tl + 1;
		tree[v].add = 0;
		
		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 );
}


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 )
	{
		if( tree[v].val )
		return tree[v].val;
	}
	
	if(tl == tr && !tree[v].val )return 0;
	
	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:74:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
apple.cpp: In function 'int main()':
apple.cpp:82: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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	190 ms	235128 KB	Output is correct
2	Correct	187 ms	235128 KB	Output is correct
3	Correct	188 ms	235256 KB	Output is correct
4	Correct	269 ms	235244 KB	Output is correct
5	Correct	268 ms	235232 KB	Output is correct
6	Correct	196 ms	235264 KB	Output is correct
7	Correct	225 ms	235256 KB	Output is correct
8	Correct	493 ms	235384 KB	Output is correct
9	Correct	538 ms	235588 KB	Output is correct
10	Correct	523 ms	235696 KB	Output is correct
11	Correct	631 ms	235512 KB	Output is correct
12	Correct	514 ms	235576 KB	Output is correct
13	Runtime error	629 ms	263168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-