Submission #750542

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
750542	2023-05-29T16:48:47 Z	MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	205 ms	71276 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)
typedef int index_t; // change to ll if needed (negligible impact on memory)
const index_t L = 1, R = 1e9;

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;
  int ch = -1;

  Node() : n(SubNode::identity()), u(Upd::noop()) {}

  void push(index_t l, index_t r) {
    index_t mid = l + (r - l) / 2;
    if (ch == -1) {
      ch = sz++;
      sz++;
    }

    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) { return qry(L, R, a, b); }
  SubNode qry(index_t l, index_t r, index_t a, index_t b) {
    if (a > r || b < l)
      return SubNode::identity();
    if (a <= l && r <= b)
      return n;

    push(l, r);
    index_t mid = l + (r - l) / 2;
    return SubNode::comb(tree[ch].qry(l, mid, a, b),
                         tree[ch + 1].qry(mid + 1, r, a, b));
  }
  void upd(index_t a, index_t b, Upd const &u) { return upd(L, R, a, b, u); }
  void upd(index_t l, index_t r, 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(l, r);
    index_t mid = l + (r - l) / 2;
    tree[ch].upd(l, mid, a, b, u);
    tree[ch + 1].upd(mid + 1, r, a, b, u);
    pull();
  }
};
Node Node::tree[MAX_NODES];
int Node::sz = 0;

void solve() {
  Node tree;
  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	32 ms	70740 KB	Output is correct
2	Correct	32 ms	70704 KB	Output is correct
3	Correct	33 ms	70696 KB	Output is correct
4	Correct	41 ms	70688 KB	Output is correct
5	Correct	41 ms	70740 KB	Output is correct
6	Correct	43 ms	70728 KB	Output is correct
7	Correct	41 ms	70768 KB	Output is correct
8	Correct	100 ms	70860 KB	Output is correct
9	Correct	168 ms	71100 KB	Output is correct
10	Correct	166 ms	71144 KB	Output is correct
11	Correct	162 ms	71072 KB	Output is correct
12	Correct	170 ms	71176 KB	Output is correct
13	Correct	153 ms	71244 KB	Output is correct
14	Correct	156 ms	71224 KB	Output is correct
15	Correct	191 ms	71184 KB	Output is correct
16	Correct	189 ms	71164 KB	Output is correct
17	Correct	165 ms	71156 KB	Output is correct
18	Correct	162 ms	71192 KB	Output is correct
19	Correct	192 ms	71140 KB	Output is correct
20	Correct	205 ms	71276 KB	Output is correct