Submission #884604

#	Time	Username	Problem	Language	Result	Execution time	Memory
884604		MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	182 ms	70736 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)
istream &__cin = cin;
#ifdef DEV_MODE
#include "debug.h"
__cinwrapper __cin_wrapper;
#define cin __cin_wrapper
#else
#define dbg(...)
#define dbg2d(...)
#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;
/******************************************************************************/

#pragma region templates

namespace ops {
template <class T> struct dummy {
  constexpr static T IDENTITY = 0;
  static T comb(T a, T b) { return a ^ b; }
};
template <class T> struct plus {
  constexpr static T IDENTITY = 0;
  static T comb(T a, T b) { return a + b; }
};
template <class T> struct times {
  constexpr static T IDENTITY = 1;
  static T comb(T a, T b) { return a * b; }
};
template <class T> struct min {
  constexpr static T IDENTITY = std::numeric_limits<T>::max();
  static T comb(T a, T b) { return std::min(a, b); }
};
template <class T> struct max {
  constexpr static T IDENTITY = std::numeric_limits<T>::min();
  static T comb(T a, T b) { return std::max(a, b); }
};
}; // namespace ops

namespace upd {
template <class T> struct add {
  T data;
  static add IDENTITY;
  static add plus_eq(T val) { return {val}; }

  void composite(add other) { data += other.data; }

  void apply(T &val, int, int, ops::dummy<T>) const { val += data; }
  void apply(T &val, int l, int r, ops::plus<T>) const {
    val += data * (r - l + 1);
  }
  void apply(T &val, int, int, ops::min<T>) const { val += data; }
  void apply(T &val, int, int, ops::max<T>) const { val += data; }
};
template <class T> add<T> add<T>::IDENTITY = {0};
template <class T> struct set {
  optional<T> data;
  static set IDENTITY;
  static set eq(T val) { return {val}; }

  void composite(set other) {
    if (other.data)
      data = other.data;
  }

  void apply(T &val, int, int, ops::dummy<T>) const {
    if (data)
      val = data.value();
  }
  void apply(T &val, int l, int r, ops::plus<T>) const {
    if (data)
      val = data.value() * (r - l + 1);
  }
  void apply(T &val, int, int, ops::min<T>) const {
    if (data)
      val = data.value();
  }
  void apply(T &val, int, int, ops::max<T>) const {
    if (data)
      val = data.value();
  }
};
template <class T> set<T> set<T>::IDENTITY = {nullopt};
template <class T> struct add_set {
  bool set;
  T data;
  static add_set IDENTITY;
  static add_set plus_eq(T val) { return {false, val}; }
  static add_set eq(T val) { return {true, val}; }

  void composite(add_set other) {
    if (other.set) {
      data = other.data;
      set = true;
    } else {
      data += other.data;
    }
  }

  void apply(T &val, int, int, ops::dummy<T>) const {
    if (set) {
      val = data;
    } else {
      val += data;
    }
  }
  void apply(T &val, int l, int r, ops::plus<T>) const {
    if (set) {
      val = data * (r - l + 1);
    } else {
      val += data * (r - l + 1);
    }
  }
  void apply(T &val, int, int, ops::min<T>) const {
    if (set) {
      val = data;
    } else {
      val += data;
    }
  }
  void apply(T &val, int, int, ops::max<T>) const {
    if (set) {
      val = data;
    } else {
      val += data;
    }
  }
};
template <class T> add_set<T> add_set<T>::IDENTITY = {false, 0};

}; // namespace upd

template <class T, class Op> class seg {
  int n;
  v<T> data;

  void pull(int p) { data[p] = Op::comb(data[2 * p], data[2 * p + 1]); }

  class leaf_reference {
    seg &par;
    int p;
    bool mutated = 0;

  public:
    leaf_reference(seg &par, int p) : par(par), p(p + par.n) {}
    operator T const &() const { return par.data[p]; }
    operator T &() {
      mutated = 1;
      return par.data[p];
    }
    T &operator=(T val) {
      mutated = 1;
      return par.data[p] = val;
    }
    ~leaf_reference() {
      if (mutated) {
        for (p >>= 1; p; p >>= 1)
          par.pull(p);
      }
    }
  };

public:
  seg(int n) : n(n), data(2 * n) { fill(all(data), Op::IDENTITY); }
  seg() : seg(0) {}
  seg(v<T> const &vals) : n(vals.size()), data(2 * n) {
    copy(vals.begin(), vals.end(), data.begin() + n);
    for (int p = n - 1; p; p--)
      pull(p);
  }
  seg(seg const &copy) : n(copy.n) {
    data = new T[2 * n];
    std::copy(copy.data, copy.data + 2 * n, data);
  }

  int size() const { return n; }

  T comb(T l, T r) const { return Op::comb(l, r); }

  T operator()(int l, int r) const {
#ifdef DEV_MODE
    assert(l >= 0);
    assert(r < n);
    assert(l <= r);
#endif
    T ra = Op::IDENTITY, rb = Op::IDENTITY;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        ra = Op::comb(ra, data[l++]);
      if (r & 1)
        rb = Op::comb(data[--r], rb);
    }
    return Op::comb(ra, rb);
  }

  leaf_reference operator[](int p) {
#ifdef DEV_MODE
    assert(p >= 0 && p < n);
#endif
    return leaf_reference(*this, p);
  }

  T const &operator[](int p) const {
#ifdef DEV_MODE
    assert(p >= 0 && p < n);
#endif
    return data[p + n];
  }
};
#define DEV_MODE_LAZY_SUPPORT
template <class T, class Op, class Upd> class lazy {
  int n;
  v<T> data;
  v<Upd> upds;

  void pull(int p) { data[p] = Op::comb(data[2 * p], data[2 * p + 1]); }
  void push(int p, int l, int mid, int r) {
    upds[p].apply(data[2 * p], l, mid, Op());
    upds[p].apply(data[2 * p + 1], mid + 1, r, Op());

    upds[2 * p].composite(upds[p]);
    upds[2 * p + 1].composite(upds[p]);

    upds[p] = Upd::IDENTITY;
  }
  T qry(int p, int l, int r, int a, int b) {
    if (a > r || b < l)
      return Op::IDENTITY;
    if (a <= l && r <= b)
      return data[p];
    int mid = (l + r) >> 1;
    push(p, l, mid, r);
    return Op::comb(qry(2 * p, l, mid, a, b), qry(2 * p + 1, mid + 1, r, a, b));
  }
  void upd(int p, int l, int r, int a, int b, Upd const &u) {
    if (a > r || b < l)
      return;
    if (a <= l && r <= b) {
      u.apply(data[p], l, r, Op());
      upds[p].composite(u);
      return;
    }
    int mid = (l + r) >> 1;
    push(p, l, mid, r);
    upd(2 * p, l, mid, a, b, u);
    upd(2 * p + 1, mid + 1, r, a, b, u);
    pull(p);
  }

  class range_reference {
    int l, r;
    lazy &par;

  public:
    range_reference(int l, int r, lazy &par) : l(l), r(r), par(par) {}

    operator T() { return par.qry(1, 0, par.n - 1, l, r); }
    void operator+=(T val) {
      par.upd(1, 0, par.n - 1, l, r, Upd::plus_eq(val));
    }
    void operator-=(T val) {
      par.upd(1, 0, par.n - 1, l, r, Upd::plus_eq(-val));
    }
    void operator=(T val) { par.upd(1, 0, par.n - 1, l, r, Upd::eq(val)); }
  };

  class leaf_reference {
    int p;
    bool mutated;
    lazy &par;

  public:
    leaf_reference(lazy &par, int p) : p(p), par(par) {}
    ~leaf_reference() {
      if (mutated) {
        int l = 0, r = par.n - 1, i = 1;
        while (l < r) {
          int mid = (l + r) >> 1;
          i <<= 1;
          par.push(p, l, mid, r);
          if (mid >= p) {
            r = mid;
          } else {
            l = mid + 1;
            i++;
          }
        }

        p += par.n;
        for (p >>= 1; p; p >>= 1)
          par.pull(p);
      }
    }

    operator T const &() const {
      par.qry(1, 0, par.n - 1, p, p);
      return par.data[p + par.n];
    }
    operator T &() {
      par.qry(1, 0, par.n - 1, p, p);
      mutated = 1;
      return par.data[p + par.n];
    }
    T &operator=(T val) {
      mutated = 1;
      return par.data[p + par.n] = val;
    }
  };

public:
  lazy(int n)
      : n(1 << (32 - __builtin_clz(max(1, n - 1)))), data(2 * this->n),
        upds(2 * this->n) {
    fill(data.begin(), data.end(), Op::IDENTITY);
    fill(upds.begin(), upds.end(), Upd::IDENTITY);
  }
  lazy() : lazy(0) {}
  lazy(v<T> const &vals)
      : n(1 << (32 - __builtin_clz(max(1, (int)vals.size() - 1)))),
        data(2 * this->n), upds(2 * this->n) {
    copy(vals.begin(), vals.end(), data.begin() + n);
    fill(data.begin() + n + vals.size(), data.end(), Op::IDENTITY);
    fill(upds.begin(), upds.begin() + 2 * n, Upd::IDENTITY);
    for (int p = n - 1; p; p--)
      pull(p);
  }

  int size() const { return n; }
  T comb(T l, T r) const { return Op::comb(l, r); }

  range_reference operator()(int l, int r) {
#ifdef DEV_MODE
    assert(l >= 0);
    assert(r < n);
    assert(l <= r);
#endif
    return range_reference(l, r, *this);
  }

  leaf_reference operator[](int p) {
#ifdef DEV_MODE
    assert(p >= 0 && p < n);
#endif
    return leaf_reference(*this, p);
  }
};

#define DEV_MODE_SPARSE_SUPPORT
template <class T, class Op, class Upd> class sparse {
  struct node {
    T data = Op::IDENTITY;
    Upd upd = Upd::IDENTITY;
    int ch = -1;
  };
  ll l, r;
  v<node> tree;

  void pull(int p) {
    tree[p].data = Op::comb(tree[tree[p].ch].data, tree[tree[p].ch + 1].data);
  }
  void push(int p, ll l, ll mid, ll r) {
    if (tree[p].ch == -1) {
      tree[p].ch = tree.size();
      tree.emplace_back();
      tree.emplace_back();
    }

    tree[p].upd.apply(tree[tree[p].ch].data, l, mid, Op());
    tree[p].upd.apply(tree[tree[p].ch + 1].data, mid + 1, r, Op());

    tree[tree[p].ch].upd.composite(tree[p].upd);
    tree[tree[p].ch + 1].upd.composite(tree[p].upd);

    tree[p].upd = Upd::IDENTITY;
  }
  T qry(int p, ll l, ll r, ll a, ll b) {
    if (a > r || b < l)
      return Op::IDENTITY;
    if (a <= l && r <= b)
      return tree[p].data;
    ll mid = l + ((r - l) >> 1);
    push(p, l, mid, r);
    return Op::comb(qry(tree[p].ch, l, mid, a, b),
                    qry(tree[p].ch + 1, mid + 1, r, a, b));
  }
  void upd(int p, ll l, ll r, ll a, ll b, Upd const &u) {
    if (a > r || b < l)
      return;
    if (a <= l && r <= b) {
      u.apply(tree[p].data, l, r, Op());
      tree[p].upd.composite(u);
      return;
    }
    ll mid = l + ((r - l) >> 1);
    push(p, l, mid, r);
    upd(tree[p].ch, l, mid, a, b, u);
    upd(tree[p].ch + 1, mid + 1, r, a, b, u);
    pull(p);
  }
  node &get_node(ll p) {
    int i = 0;
    ll l = this->l, r = this->r;
    while (l < r) {
      ll mid = l + ((r - l) >> 1);
      push(i, l, mid, r);
      if (p <= mid) {
        r = mid;
        i = tree[i].ch;
      } else {
        l = mid + 1;
        i = tree[i].ch + 1;
      }
    }
    return tree[i];
  }
  void pull_node(ll i, int p, ll l, ll r) {
    if (l < r) {
      ll mid = l + ((r - l) >> 1);
      push(p, l, mid, r);
      if (i <= mid) {
        pull_node(i, tree[p].ch, l, mid);
      } else {
        pull_node(i, tree[p].ch + 1, mid + 1, r);
      }
      pull(p);
    }
  }
  void pull_node(ll i) { pull_node(i, 0, l, r); }

  class range_reference {
    ll l, r;
    sparse &par;

  public:
    range_reference(ll l, ll r, sparse &par) : l(l), r(r), par(par) {}

    operator T() { return par.qry(0, par.l, par.r, l, r); }
    void operator+=(T val) {
      par.upd(0, par.l, par.r, l, r, Upd::plus_eq(val));
    }
    void operator-=(T val) {
      par.upd(0, par.l, par.r, l, r, Upd::plus_eq(-val));
    }
    void operator=(T val) { par.upd(0, par.l, par.r, l, r, Upd::eq(val)); }
  };

  class leaf_reference {
    ll p;
    bool mutated;
    sparse &par;

  public:
    leaf_reference(sparse &par, ll p) : p(p), par(par) {}
    ~leaf_reference() {
      if (mutated) {
        par.pull_node(p);
      }
    }

    operator T const &() const { return par.get_node(p).data; }
    operator T &() {
      mutated = 1;
      return par.get_node(p).data;
    }
    T &operator=(T val) {
      mutated = 1;
      return par.get_node(p).data = val;
    }
  };

public:
  sparse(ll l, ll r) : l(l), r(r) {
    tree.push_back({Op::IDENTITY, Upd::IDENTITY, -1});
  }
  sparse() : sparse(0) {}

  ll size() const { return r - l + 1; }
  ll left() const { return l; }
  ll right() const { return r; }

  // reserve capacity for `size` nodes
  // set size = 2 * Q * log(N)
  void reserve(size_t size) { tree.reserve(size); }

  range_reference operator()(ll l, ll r) {
#ifdef DEV_MODE
    assert(l >= this->l);
    assert(r <= this->r);
    assert(l <= r);
#endif
    return range_reference(l, r, *this);
  }

  leaf_reference operator[](ll p) {
#ifdef DEV_MODE
    assert(p >= this->l && p <= this->r);
#endif
    return leaf_reference(*this, p);
  }
};
#pragma endregion templates

void solve() {
  int m;
  cin >> m;

  sparse<int, ops::plus<int>, upd::set<int>> seg(1, 1e9);
  seg.reserve(6000000);

  int c = 0;
  while (m--) {
    int d, x, y;
    cin >> d >> x >> y;
    x += c;
    y += c;

    if (d == 1) {
      cout << (c = seg(x, y)) << '\n';
    } else {
      seg(x, y) = 1;
    }
  }
}

int main() {
#ifdef DEV_MODE
  debug_start(INTERACTIVE, "misc-in.txt");
#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

Compilation message (stderr)

apple.cpp:57: warning: ignoring '#pragma region templates' [-Wunknown-pragmas]
   57 | #pragma region templates
      | 
apple.cpp:543: warning: ignoring '#pragma endregion templates' [-Wunknown-pragmas]
  543 | #pragma endregion templates
      |

• Subtask 1: 100 / 100