Submission #680412

#	Time	Username	Problem	Language	Result	Execution time	Memory
680412		MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	533 ms	207776 KiB

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
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';
#define dbgp(x)                                                                \
  cerr << "[" << __LINE__ << "] " << #x << " = {" << (x).f << ", " << (x).s    \
       << "}" << '\n';
#else
#define dbg(x)
#define dbgp(x)
#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;
}

// MULTITEST TOGGLE
const bool MULTITEST = false;
/******************************************************************************/
struct Node {
  Node(ll l, ll r) : l(l), r(r) {}
  ~Node() {
    delete left;
    delete right;
  }

  int val = 0, set = 0;
  int l, r;
  Node *left = nullptr, *right = nullptr;

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

    if (set != 0) {
      left->set = 1;
      right->set = 1;
      left->val = mid - l + 1;
      right->val = r - mid;
      set = 0;
    }
  }
  void pull() { val = left->val + right->val; }

  ll qry(int a, int b) {
    if (a > r || b < l)
      return 0;
    if (a <= l && r <= b) {
      return val;
    }

    push();
    return left->qry(a, b) + right->qry(a, b);
  }
  void upd(int a, int b) {
    if (a > r || b < l)
      return;
    if (a <= l && r <= b) {
      val = r - l + 1;
      set = 1;
      return;
    }
    push();
    left->upd(a, b);
    right->upd(a, b);
    pull();
  }
};

void solve() {
  int m;
  cin >> m;

  Node seg(0, 1e9);

  int c = 0;
  while (m--) {
    int d, x, y;
    cin >> d >> x >> y;
    if (d == 1) {
      int res = seg.qry(x + c, y + c);
      cout << res << '\n';
      c = res;
    } else {
      seg.upd(x + c, y + c);
    }
  }
}

int main() {
#ifdef DEV_MODE
  freopen("misc-in.txt", "r", stdin);
#else
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int t;
  if (MULTITEST)
    cin >> t;
  else
    t = 1;
  while (t--)
    solve();
}

• Subtask 1: 100 / 100