Submission #93463

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93463	2019-01-08T14:38:35 Z	mirbek01	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	576 ms	159736 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){
            if(tl != tr){
                  tree[ tree[v].l ].add = tree[ tree[v].r ].add = 1;
            }
		tree[v].val = tr - tl + 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:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
apple.cpp: In function 'int main()':
apple.cpp:73: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	109 ms	156920 KB	Output is correct
2	Correct	106 ms	156892 KB	Output is correct
3	Correct	110 ms	156796 KB	Output is correct
4	Correct	122 ms	156924 KB	Output is correct
5	Correct	126 ms	156920 KB	Output is correct
6	Correct	127 ms	156920 KB	Output is correct
7	Correct	129 ms	156892 KB	Output is correct
8	Correct	250 ms	157096 KB	Output is correct
9	Correct	398 ms	157380 KB	Output is correct
10	Correct	426 ms	157320 KB	Output is correct
11	Correct	458 ms	157264 KB	Output is correct
12	Correct	438 ms	157276 KB	Output is correct
13	Correct	439 ms	159736 KB	Output is correct
14	Correct	420 ms	159580 KB	Output is correct
15	Correct	576 ms	159736 KB	Output is correct
16	Correct	550 ms	159708 KB	Output is correct
17	Correct	404 ms	159552 KB	Output is correct
18	Correct	384 ms	159608 KB	Output is correct
19	Correct	459 ms	159608 KB	Output is correct
20	Correct	461 ms	159692 KB	Output is correct