Submission #736556

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
736556	2023-05-05T23:48:19 Z	MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	379 ms	207784 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)
#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;
/******************************************************************************/

typedef int index_t;

struct SubNode {
  int x;

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

  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 mem[];
  Node(index_t l, index_t r)
      : n(SubNode::identity()), u(Upd::noop()), l(l), r(r) {}

#ifdef DEV_MODE
  // leak all over the grading servers
  ~Node() {
    delete left;
    delete right;
  }
#endif

  SubNode n;
  Upd u;
  index_t l, r;
  Node *left = nullptr, *right = nullptr;

  void push() {
    index_t mid = l + (r - l) / 2;
    if (left == nullptr) {
      left = new Node(l, mid);
    }
    if (right == nullptr) {
      right = new Node(mid + 1, r);
    }

    u.apply(left->n, mid - l + 1, l, mid);
    u.apply(right->n, r - mid, mid + 1, r);
    left->u.add(u);
    right->u.add(u);
    u = Upd::noop();
  }
  void pull() { n = SubNode::comb(left->n, right->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(left->qry(a, b), right->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();
    left->upd(a, b, u);
    right->upd(a, b, u);
    pull();
  }
};

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);
  cerr << setprecision(20);
#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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	12 ms	4896 KB	Output is correct
5	Correct	16 ms	5968 KB	Output is correct
6	Correct	14 ms	5844 KB	Output is correct
7	Correct	14 ms	5932 KB	Output is correct
8	Correct	120 ms	44576 KB	Output is correct
9	Correct	225 ms	77276 KB	Output is correct
10	Correct	244 ms	85376 KB	Output is correct
11	Correct	248 ms	91596 KB	Output is correct
12	Correct	249 ms	94472 KB	Output is correct
13	Correct	222 ms	109912 KB	Output is correct
14	Correct	220 ms	110980 KB	Output is correct
15	Correct	357 ms	201764 KB	Output is correct
16	Correct	356 ms	203132 KB	Output is correct
17	Correct	230 ms	114744 KB	Output is correct
18	Correct	227 ms	114816 KB	Output is correct
19	Correct	362 ms	207784 KB	Output is correct
20	Correct	379 ms	207696 KB	Output is correct