Submission #792367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792367	2023-07-25T03:25:32 Z	asdfgrace	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	304 ms	228372 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 * 3 / 2);
  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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	276 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	468 KB	Output is correct
4	Correct	14 ms	18380 KB	Output is correct
5	Correct	17 ms	22904 KB	Output is correct
6	Correct	17 ms	22880 KB	Output is correct
7	Correct	18 ms	22888 KB	Output is correct
8	Correct	107 ms	113172 KB	Output is correct
9	Correct	239 ms	226124 KB	Output is correct
10	Correct	234 ms	226056 KB	Output is correct
11	Correct	240 ms	226100 KB	Output is correct
12	Correct	242 ms	226032 KB	Output is correct
13	Correct	209 ms	226232 KB	Output is correct
14	Correct	214 ms	226212 KB	Output is correct
15	Correct	287 ms	228300 KB	Output is correct
16	Correct	288 ms	228360 KB	Output is correct
17	Correct	211 ms	228276 KB	Output is correct
18	Correct	212 ms	228232 KB	Output is correct
19	Correct	284 ms	228372 KB	Output is correct
20	Correct	304 ms	228320 KB	Output is correct