Submission #597772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
597772	2022-07-16T20:44:43 Z	Shreyan_Paliwal	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	409 ms	188620 KB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

struct Node {
  int sum, lazy, tl, tr, l, r;
  Node() : sum(0), lazy(0), l(-1), r(-1) {}
};

const int MAXN = 123456;
Node      segtree[64 * MAXN];
int       cnt = 2;

void push_lazy(int node) {
  if (segtree[node].lazy) {
    segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
    int mid           = (segtree[node].tl + segtree[node].tr) / 2;
    if (segtree[node].l == -1) {
      segtree[node].l             = cnt++;
      segtree[segtree[node].l].tl = segtree[node].tl;
      segtree[segtree[node].l].tr = mid;
    }
    if (segtree[node].r == -1) {
      segtree[node].r             = cnt++;
      segtree[segtree[node].r].tl = mid + 1;
      segtree[segtree[node].r].tr = segtree[node].tr;
    }
    segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
    segtree[node].lazy                                            = 0;
  }
}

void update(int node, int l, int r) {
  push_lazy(node);
  if (l == segtree[node].tl && r == segtree[node].tr) {
    segtree[node].lazy = 1;
    push_lazy(node);
  } else {
    int mid = (segtree[node].tl + segtree[node].tr) / 2;
    if (segtree[node].l == -1) {
      segtree[node].l             = cnt++;
      segtree[segtree[node].l].tl = segtree[node].tl;
      segtree[segtree[node].l].tr = mid;
    }
    if (segtree[node].r == -1) {
      segtree[node].r             = cnt++;
      segtree[segtree[node].r].tl = mid + 1;
      segtree[segtree[node].r].tr = segtree[node].tr;
    }

    if (l > mid)
      update(segtree[node].r, l, r);
    else if (r <= mid)
      update(segtree[node].l, l, r);
    else {
      update(segtree[node].l, l, mid);
      update(segtree[node].r, mid + 1, r);
    }

    push_lazy(segtree[node].l);
    push_lazy(segtree[node].r);
    segtree[node].sum = segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
  }
}

int query(int node, int l, int r) {
  push_lazy(node);
  if (l == segtree[node].tl && r == segtree[node].tr)
    return segtree[node].sum;
  else {
    int mid = (segtree[node].tl + segtree[node].tr) / 2;
    if (segtree[node].l == -1) {
      segtree[node].l             = cnt++;
      segtree[segtree[node].l].tl = segtree[node].tl;
      segtree[segtree[node].l].tr = mid;
    }
    if (segtree[node].r == -1) {
      segtree[node].r             = cnt++;
      segtree[segtree[node].r].tl = mid + 1;
      segtree[segtree[node].r].tr = segtree[node].tr;
    }

    if (l > mid)
      return query(segtree[node].r, l, r);
    else if (r <= mid)
      return query(segtree[node].l, l, r);
    else
      return query(segtree[node].l, l, mid) + query(segtree[node].r, mid + 1, r);
  }
}

int main() {
  cin.tie(nullptr)->ios::sync_with_stdio(false);

  // freopen("main.in", "r", stdin);

  int m;
  cin >> m;

  segtree[1].sum  = 0;
  segtree[1].lazy = 0;
  segtree[1].tl   = 1;
  segtree[1].tr   = 1e9;

  int c = 0;
  FOR(_, 0, m) {
    int d, x, y;
    cin >> d >> x >> y;
    if (d == 1) {
      c = query(1, x + c, y + c);
      cout << c << '\n';
    } else
      update(1, x + c, y + c);
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	74 ms	185804 KB	Output is correct
2	Correct	81 ms	185780 KB	Output is correct
3	Correct	78 ms	185752 KB	Output is correct
4	Correct	86 ms	185920 KB	Output is correct
5	Correct	88 ms	186108 KB	Output is correct
6	Correct	87 ms	186004 KB	Output is correct
7	Correct	91 ms	186048 KB	Output is correct
8	Correct	174 ms	186860 KB	Output is correct
9	Correct	295 ms	187944 KB	Output is correct
10	Correct	320 ms	187996 KB	Output is correct
11	Correct	305 ms	188008 KB	Output is correct
12	Correct	333 ms	187916 KB	Output is correct
13	Correct	265 ms	188348 KB	Output is correct
14	Correct	296 ms	188484 KB	Output is correct
15	Correct	368 ms	188476 KB	Output is correct
16	Correct	409 ms	188440 KB	Output is correct
17	Correct	281 ms	188320 KB	Output is correct
18	Correct	306 ms	188424 KB	Output is correct
19	Correct	376 ms	188492 KB	Output is correct
20	Correct	377 ms	188620 KB	Output is correct