Submission #318818

#TimeUsernameProblemLanguageResultExecution timeMemory
318818tushar_2658Monkey and Apple-trees (IZhO12_apple)C++14
100 / 100
684 ms243044 KiB
#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 (stderr)

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);
      |                 ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...