Submission #680411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
680411	2023-01-10T17:55:51 Z	MattTheNub	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	403 ms	262144 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;
  }

  ll val = 0, set = 0;
  ll 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	14 ms	6484 KB	Output is correct
5	Correct	18 ms	7892 KB	Output is correct
6	Correct	17 ms	7588 KB	Output is correct
7	Correct	21 ms	7892 KB	Output is correct
8	Correct	156 ms	58904 KB	Output is correct
9	Correct	309 ms	102436 KB	Output is correct
10	Correct	328 ms	113072 KB	Output is correct
11	Correct	344 ms	121444 KB	Output is correct
12	Correct	344 ms	125132 KB	Output is correct
13	Correct	357 ms	145668 KB	Output is correct
14	Correct	322 ms	147076 KB	Output is correct
15	Runtime error	403 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-