Submission #750539

#	Time	Username	Problem	Language	Result	Execution time	Memory
750539		MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	317 ms	120400 KiB

apple

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <class T> using v = vector<T>;
using ll = long long;
using dd = long double;
using int2 = pair<int, int>;
using ll2 = pair<ll, ll>;
using dd2 = pair<dd, dd>;

#define f first
#define s second
#define all(x) begin(x), end(x)
#ifdef DEV_MODE
#include "debug.h"
#else
#define dbg(...)
#endif

template <class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
  in >> p.first >> p.second;
  return in;
}
template <class T> istream &operator>>(istream &in, v<T> &v) {
  for (auto &x : v)
    in >> x;
  return in;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
 _______________________________________
( If you don't fail at least 90% of the )
( time, you're not aiming high enough.  )
(                                       )
( - Alan Kay                            )
 ---------------------------------------
        o   ^__^
         o  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||
*/

const bool INTERACTIVE = false;
const bool MULTITEST = false;
/******************************************************************************/

const size_t MAX_NODES = 6000000; // 2 * Q * log(N) (default is Q=2e5, N=1e9)

// memory usage is 2 * Q * s * log(N) + O(1)
// where s = size of SubNode + Upd + 12 bytes, aligned to 4 bytes
// (assuming a 64-bit target)
// (upper bound; actual memory usage is lower for large Q/small N)
typedef int index_t; // change to ll if needed (increases s by 8 bytes)

struct SubNode {
  int x;

  static constexpr SubNode identity() { return SubNode(); }

  static SubNode comb(const SubNode &l, const SubNode &r) {
    return {l.x + r.x};
  }
};

struct Upd {
  bool active;

  static constexpr Upd noop() { return {false}; }

  void apply(SubNode &n, index_t width, index_t l, index_t r) const {
    if (active) {
      n.x = width;
    }
  }

  void add(Upd const &u) { active |= u.active; }
};

struct Node {
  static Node tree[MAX_NODES];
  static int sz;
  SubNode n;
  Upd u;
  index_t l, r;
  int ch = -1;

  Node() {}
  Node(index_t l, index_t r)
      : n(SubNode::identity()), u(Upd::noop()), l(l), r(r) {}

  void push() {
    index_t mid = l + (r - l) / 2;
    if (ch == -1) {
      tree[ch = sz++] = Node(l, mid);
      tree[sz++] = Node(mid + 1, r);
    }

    u.apply(tree[ch].n, mid - l + 1, l, mid);
    u.apply(tree[ch + 1].n, r - mid, mid + 1, r);
    tree[ch].u.add(u);
    tree[ch + 1].u.add(u);
    u = Upd::noop();
  }
  void pull() { n = SubNode::comb(tree[ch].n, tree[ch + 1].n); }

  SubNode qry(index_t a, index_t b) {
    if (a > r || b < l)
      return SubNode::identity();
    if (a <= l && r <= b)
      return n;

    push();
    return SubNode::comb(tree[ch].qry(a, b), tree[ch + 1].qry(a, b));
  }
  void upd(index_t a, index_t b, Upd const &u) {
    if (a > r || b < l)
      return;
    if (a <= l && r <= b) {
      u.apply(n, r - l + 1, l, r);
      this->u = u;
      return;
    }
    push();
    tree[ch].upd(a, b, u);
    tree[ch + 1].upd(a, b, u);
    pull();
  }
};
Node Node::tree[MAX_NODES];
int Node::sz = 0;

void solve() {
  Node tree(1, 1e9);
  int m;
  cin >> m;
  int c = 0;
  while (m--) {
    int d, l, r;
    cin >> d >> l >> r;
    l += c;
    r += c;
    if (d == 1) {
      cout << (c = tree.qry(l, r).x) << '\n';
    } else {
      tree.upd(l, r, {true});
    }
  }
}

int main() {
#ifdef DEV_MODE
  if (!INTERACTIVE)
    freopen("misc-in.txt", "r", stdin);
  debug_start();
#else
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#endif

  int t;
  if (MULTITEST)
    cin >> t;
  else
    t = 1;
  while (t--)
    solve();

#ifdef DEV_MODE
  debug_exit(INTERACTIVE);
#endif
}
#ifdef DEV_MODE
#include "debug.cpp"
#endif

• Subtask 1: 100 / 100