Submission #93457

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93457	2019-01-08T13:55:02 Z	Aydarov03	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	714 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 )
		{
			ans.push_back( c = get( l , r ) );
		}
		
		if( tp == 2 )
			upd(l , r);
	}
	
	for(auto c : ans)cout << c << endl;
	
}

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	163 ms	235128 KB	Output is correct
2	Correct	161 ms	235256 KB	Output is correct
3	Correct	162 ms	235160 KB	Output is correct
4	Correct	225 ms	235236 KB	Output is correct
5	Correct	215 ms	235256 KB	Output is correct
6	Correct	212 ms	235256 KB	Output is correct
7	Correct	226 ms	235324 KB	Output is correct
8	Correct	464 ms	236536 KB	Output is correct
9	Correct	659 ms	237812 KB	Output is correct
10	Correct	586 ms	237760 KB	Output is correct
11	Correct	714 ms	237816 KB	Output is correct
12	Correct	568 ms	237816 KB	Output is correct
13	Runtime error	663 ms	263168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-