Submission #884598

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884598	2023-12-07T18:07:00 Z	MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	236 ms	136120 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; }

  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);

  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:539: warning: ignoring '#pragma endregion templates' [-Wunknown-pragmas]
  539 | #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	9 ms	2644 KB	Output is correct
5	Correct	12 ms	2776 KB	Output is correct
6	Correct	12 ms	2776 KB	Output is correct
7	Correct	11 ms	2776 KB	Output is correct
8	Correct	68 ms	18116 KB	Output is correct
9	Correct	149 ms	35504 KB	Output is correct
10	Correct	152 ms	35760 KB	Output is correct
11	Correct	145 ms	36016 KB	Output is correct
12	Correct	145 ms	35348 KB	Output is correct
13	Correct	149 ms	69676 KB	Output is correct
14	Correct	143 ms	69800 KB	Output is correct
15	Correct	234 ms	135884 KB	Output is correct
16	Correct	207 ms	134384 KB	Output is correct
17	Correct	143 ms	68688 KB	Output is correct
18	Correct	155 ms	70528 KB	Output is correct
19	Correct	234 ms	135644 KB	Output is correct
20	Correct	236 ms	136120 KB	Output is correct