Submission #680412

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
680412	2023-01-10T17:56:54 Z	MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	533 ms	207776 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
#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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	13 ms	4812 KB	Output is correct
5	Correct	18 ms	5884 KB	Output is correct
6	Correct	16 ms	5588 KB	Output is correct
7	Correct	17 ms	5844 KB	Output is correct
8	Correct	153 ms	43620 KB	Output is correct
9	Correct	295 ms	75672 KB	Output is correct
10	Correct	312 ms	83724 KB	Output is correct
11	Correct	302 ms	89932 KB	Output is correct
12	Correct	322 ms	92676 KB	Output is correct
13	Correct	307 ms	107844 KB	Output is correct
14	Correct	295 ms	108864 KB	Output is correct
15	Correct	533 ms	201820 KB	Output is correct
16	Correct	517 ms	203232 KB	Output is correct
17	Correct	292 ms	114776 KB	Output is correct
18	Correct	314 ms	114920 KB	Output is correct
19	Correct	495 ms	207756 KB	Output is correct
20	Correct	500 ms	207776 KB	Output is correct