Submission #318818

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
318818	2020-11-03T09:48:46 Z	tushar_2658	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	684 ms	243044 KB

apple

#include "bits/stdc++.h"
using namespace std;

const int maxn = 100005;

struct NODE {
  NODE *l, *r;
  int val, lazy;
  NODE(){
    l = NULL; r = NULL; val = lazy = 0;
  }
};

void push_down(NODE *cur, int b, int e){
  if(cur -> lazy){
    cur -> val = (e - b + 1);
    if(cur -> l == NULL)cur -> l = new NODE();
    if(cur -> r == NULL)cur -> r = new NODE();
    cur -> l -> lazy = 1;
    cur -> r -> lazy = 1;
    cur -> lazy = 0;
  }
}

void upd(NODE *cur, int b, int e, int i, int j){
  push_down(cur, b, e);
  if(i > e or j < b or i > j or b > e)return;
  if(b >= i && j >= e){
    cur -> lazy = 1;
    push_down(cur, b, e);
    return;
  }  
  int mid = (b + e) >> 1;
  if(cur -> r == NULL)cur -> r = new NODE();
  if(cur -> l == NULL)cur -> l = new NODE();
  upd(cur -> l, b, mid, i, j);
  upd(cur -> r, mid + 1, e, i, j);
  cur -> val = cur -> l -> val + cur -> r -> val;
}

int query(NODE *cur, int b, int e, int i, int j){
  if(i > e or j < b or i > j or b > e)return 0;
  push_down(cur, b, e);
  if(b >= i && j >= e){
    return cur -> val;
  }
  int mid = (b + e) >> 1;
  if(cur -> l == NULL)cur -> l = new NODE();
  if(cur -> r == NULL)cur -> r = new NODE();
  return query(cur -> l, b, mid, i, j) + query(cur -> r, mid + 1, e, i, j);
}

int main(int argc, char const *argv[])
{
  int q;
  scanf("%d", &q);
  NODE *root = new NODE();
  int c = 0;
  while(q--){
    int type;
    scanf("%d", &type);
    if(type == 2){
      int l, r; scanf("%d %d", &l, &r);
      upd(root, 1, 1e9, l + c, r + c);
    }else {
      int l, r; scanf("%d %d", &l, &r);
      int ans = query(root, 1, 1e9, l + c, r + c);
      c = ans;
      printf("%d\n", ans);
    }
  }

  return 0;
}

Compilation message

apple.cpp: In function 'int main(int, const char**)':
apple.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
apple.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%d", &type);
      |     ~~~~~^~~~~~~~~~~~~
apple.cpp:63:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |       int l, r; scanf("%d %d", &l, &r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~
apple.cpp:66:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |       int l, r; scanf("%d %d", &l, &r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	20 ms	5868 KB	Output is correct
5	Correct	24 ms	6980 KB	Output is correct
6	Correct	25 ms	6796 KB	Output is correct
7	Correct	24 ms	7012 KB	Output is correct
8	Correct	201 ms	52324 KB	Output is correct
9	Correct	420 ms	91032 KB	Output is correct
10	Correct	414 ms	100424 KB	Output is correct
11	Correct	437 ms	107748 KB	Output is correct
12	Correct	447 ms	110928 KB	Output is correct
13	Correct	392 ms	128228 KB	Output is correct
14	Correct	399 ms	129764 KB	Output is correct
15	Correct	649 ms	236092 KB	Output is correct
16	Correct	671 ms	237780 KB	Output is correct
17	Correct	397 ms	134116 KB	Output is correct
18	Correct	396 ms	134244 KB	Output is correct
19	Correct	684 ms	242892 KB	Output is correct
20	Correct	675 ms	243044 KB	Output is correct