Submission #887411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
887411	2023-12-14T13:12:47 Z	Zero_OP	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	196 ms	55752 KB

apple

#include<bits/stdc++.h>

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
  if(a > b) return a = b, true;
  return false;
}

template<class T> bool maximize(T& a, T b){
  if(a < b) return a = b, true;
  return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 1e7 + 5;

int timerNodes = 0, lc[N], rc[N], st[N];
bitset<N> lzy;

void apply(int cur, int l, int r){
  st[cur] = (r - l + 1);
  lzy[cur] = true;
}

void pushDown(int cur, int l, int r, int mid){
  if(lzy[cur]){
    apply(lc[cur], l, mid);
    apply(rc[cur], mid + 1, r);
    lzy[cur] = false;
  }
}

void extend(int cur){
  if(lc[cur] == 0) lc[cur] = ++timerNodes;
  if(rc[cur] == 0) rc[cur] = ++timerNodes;
}

void update(int cur, int l, int r, int u, int v){
  if(v < l or u > r) return;
  if(u <= l and r <= v){
    apply(cur, l, r);
  }
  else{
    int mid = l + r >> 1;
    extend(cur);
    pushDown(cur, l, r, mid);
    update(lc[cur], l, mid, u, v);
    update(rc[cur], mid + 1, r, u, v);
    st[cur] = st[lc[cur]] + st[rc[cur]];
  }
}

int query(int cur, int l, int r, int u, int v){
  if(v < l or u > r) return 0;
  if(u <= l and r <= v){
    return st[cur];
  }
  int mid = l + r >> 1;
  extend(cur);
  pushDown(cur, l, r, mid);
  return query(lc[cur], l, mid, u, v) + query(rc[cur], mid + 1, r, u, v);
}

void Zero_OP(){
  int q, c = 0, lim = 1e9;
  cin >> q;
  while(q--){
    int d, x, y;
    cin >> d >> x >> y;
    x += c, y += c;
    if(d == 1){
      c = query(0, 1, lim, x, y);
      cout << c << '\n';
    }
    else{
      update(0, 1, lim, x, y);
    }
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  #define task "antuvu"
  if(fopen(task".inp", "r")){
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
  }

  Zero_OP();

  return 0;
}

Compilation message

apple.cpp: In function 'void update(int, int, int, int, int)':
apple.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = l + r >> 1;
      |               ~~^~~
apple.cpp: In function 'int query(int, int, int, int, int)':
apple.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid = l + r >> 1;
      |             ~~^~~
apple.cpp: In function 'int main()':
apple.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	8 ms	1676 KB	Output is correct
5	Correct	10 ms	3420 KB	Output is correct
6	Correct	13 ms	3672 KB	Output is correct
7	Correct	9 ms	3420 KB	Output is correct
8	Correct	69 ms	13904 KB	Output is correct
9	Correct	145 ms	23460 KB	Output is correct
10	Correct	146 ms	24652 KB	Output is correct
11	Correct	141 ms	26704 KB	Output is correct
12	Correct	161 ms	28244 KB	Output is correct
13	Correct	133 ms	30288 KB	Output is correct
14	Correct	132 ms	31316 KB	Output is correct
15	Correct	194 ms	54096 KB	Output is correct
16	Correct	177 ms	54980 KB	Output is correct
17	Correct	128 ms	34148 KB	Output is correct
18	Correct	125 ms	34128 KB	Output is correct
19	Correct	196 ms	55408 KB	Output is correct
20	Correct	190 ms	55752 KB	Output is correct