Submission #750539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
750539	2023-05-29T16:38:43 Z	MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	317 ms	120400 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;
/******************************************************************************/

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	117684 KB	Output is correct
2	Correct	55 ms	117636 KB	Output is correct
3	Correct	45 ms	117724 KB	Output is correct
4	Correct	63 ms	117948 KB	Output is correct
5	Correct	69 ms	117836 KB	Output is correct
6	Correct	60 ms	117896 KB	Output is correct
7	Correct	63 ms	117840 KB	Output is correct
8	Correct	141 ms	118732 KB	Output is correct
9	Correct	229 ms	119784 KB	Output is correct
10	Correct	251 ms	119836 KB	Output is correct
11	Correct	224 ms	119812 KB	Output is correct
12	Correct	231 ms	119908 KB	Output is correct
13	Correct	245 ms	120252 KB	Output is correct
14	Correct	221 ms	120244 KB	Output is correct
15	Correct	272 ms	120348 KB	Output is correct
16	Correct	300 ms	120336 KB	Output is correct
17	Correct	200 ms	120216 KB	Output is correct
18	Correct	222 ms	120272 KB	Output is correct
19	Correct	285 ms	120284 KB	Output is correct
20	Correct	317 ms	120400 KB	Output is correct