Submission #792367

#	Time	Username	Problem	Language	Result	Execution time	Memory
792367		asdfgrace	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	304 ms	228372 KiB

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 / 100