Submission #792349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792349	2023-07-25T02:20:54 Z	asdfgrace	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	288 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
#define PAR2D(x) DEBUG(PRINT(#x << ":\n"); for (auto arr : x) {PAR(arr);} PRINT('\n'));
using i64 = long long;
constexpr int INF = 1000000007; //998244353;

template <typename T> struct Node {
  T val, upd;
  int lc, rc, l, r;
  Node() {
    val = upd = 0;
    lc = rc = -1;
  }
};

template <typename T> struct DynamicST {
  int n, cur = 2;
  vector<Node<int>> st;
  
  DynamicST(int _n) {
    n = _n;
    st.resize(64 * n, Node<int>());
    st[1].val = st[1].upd = 0;
    st[1].l = 1;
    st[1].r = INF;
  }
  
  void addch(int at) {
    int m = (st[at].l + st[at].r) >> 1;
    if (st[at].lc == -1) {
      st[at].lc = cur;
      st[cur].l = st[at].l;
      st[cur].r = m;
      ++cur;
    }
    if (st[at].rc == -1) {
      st[at].rc = cur;
      st[cur].l = m + 1;
      st[cur].r = st[at].r;
      ++cur;
    }
  }
  
  void pushdown(int at) {
    if (st[at].upd == 0) return;
    st[at].val = st[at].r - st[at].l + 1;
    addch(at);
    st[st[at].lc].upd = st[st[at].rc].upd = 1;
    st[at].upd = 0;
  }
  
  void update(int at, int l, int r) {
    if (r < l) return;
    //PV(l); PV(r);
    pushdown(at);
    if (l == st[at].l && r == st[at].r) {
      st[at].upd = 1;
      pushdown(at);
    } else {
      addch(at);
      //PV(st[at].lc); PV(st[at].rc);
      int mid = (st[at].l + st[at].r) / 2;
      if (mid < l) {
        update(st[at].rc, l, r);
      } else if (mid >= r) {
        update(st[at].lc, l, r);
      } else {
        update(st[at].lc, l, mid);
        update(st[at].rc, mid + 1, r);
      }
      pushdown(st[at].lc);
      pushdown(st[at].rc);
      st[at].val = st[st[at].lc].val + st[st[at].rc].val;
    }
  }
  
  T quer(int at, int l, int r) {
    if (r < l) return 0;
    assert(at != -1);
    pushdown(at);
    if (l == st[at].l && r == st[at].r) {
      return st[at].val;
    }
    addch(at);
    int mid = (st[at].l + st[at].r) / 2;
    if (mid < l) {
      return quer(st[at].rc, l, r);
    } else if (mid >= r) {
      return quer(st[at].lc, l, r);
    } else {
      return quer(st[at].lc, l, mid) + quer(st[at].rc, mid + 1, r);
    }
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int q; cin >> q;
  i64 c = 0;
  DynamicST<int> st(q);
  while (q--) {
    i64 t, l, r;
    cin >> t >> l >> r;
    l += c; r += c;
    if (t == 1) {
      int res = st.quer(1, l, r);
      cout << res << '\n';
      c = res;
    } else {
      st.update(1, l, r);
    }
  }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	13 ms	12408 KB	Output is correct
5	Correct	16 ms	15544 KB	Output is correct
6	Correct	15 ms	15532 KB	Output is correct
7	Correct	16 ms	15444 KB	Output is correct
8	Correct	96 ms	76432 KB	Output is correct
9	Correct	211 ms	152704 KB	Output is correct
10	Correct	230 ms	152720 KB	Output is correct
11	Correct	231 ms	152856 KB	Output is correct
12	Correct	246 ms	152672 KB	Output is correct
13	Correct	197 ms	153176 KB	Output is correct
14	Correct	189 ms	153080 KB	Output is correct
15	Runtime error	288 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-