Submission #280733

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
280733	2020-08-23T01:27:12 Z	milleniumEeee	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	592 ms	159612 KB

apple

// molodoy-neopitniy
#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;
  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 );
  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:73:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main()
      |      ^
apple.cpp: In function 'int main()':
apple.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d%d%d" , &tp , &l , &r );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	156808 KB	Output is correct
2	Correct	99 ms	156920 KB	Output is correct
3	Correct	98 ms	156920 KB	Output is correct
4	Correct	122 ms	157052 KB	Output is correct
5	Correct	140 ms	157208 KB	Output is correct
6	Correct	139 ms	157216 KB	Output is correct
7	Correct	126 ms	157048 KB	Output is correct
8	Correct	298 ms	157988 KB	Output is correct
9	Correct	578 ms	159164 KB	Output is correct
10	Correct	559 ms	159188 KB	Output is correct
11	Correct	472 ms	159128 KB	Output is correct
12	Correct	506 ms	159028 KB	Output is correct
13	Correct	489 ms	159480 KB	Output is correct
14	Correct	525 ms	159480 KB	Output is correct
15	Correct	550 ms	159480 KB	Output is correct
16	Correct	535 ms	159552 KB	Output is correct
17	Correct	449 ms	159536 KB	Output is correct
18	Correct	451 ms	159480 KB	Output is correct
19	Correct	592 ms	159584 KB	Output is correct
20	Correct	589 ms	159612 KB	Output is correct