Submission #884604

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884604	2023-12-07T18:09:20 Z	MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	182 ms	70736 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	8 ms	3676 KB	Output is correct
5	Correct	10 ms	2856 KB	Output is correct
6	Correct	10 ms	3884 KB	Output is correct
7	Correct	10 ms	2908 KB	Output is correct
8	Correct	62 ms	17344 KB	Output is correct
9	Correct	134 ms	27220 KB	Output is correct
10	Correct	129 ms	28756 KB	Output is correct
11	Correct	140 ms	30888 KB	Output is correct
12	Correct	152 ms	33124 KB	Output is correct
13	Correct	127 ms	36944 KB	Output is correct
14	Correct	124 ms	36944 KB	Output is correct
15	Correct	182 ms	67456 KB	Output is correct
16	Correct	172 ms	69156 KB	Output is correct
17	Correct	130 ms	39068 KB	Output is correct
18	Correct	126 ms	38996 KB	Output is correct
19	Correct	180 ms	70736 KB	Output is correct
20	Correct	173 ms	70212 KB	Output is correct