Submission #822965

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
822965	2023-08-12T06:11:51 Z	arush_agu	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	276 ms	262144 KB

apple

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9 + 100;
const ld EPS = 1e-9;

const int MAX_NODES = 1e5 * 35;

struct Node {
  ll l = -1, r = -1, val;
  int l_idx = -1, r_idx = -1;
  bool lazy = 0;
} nodes[MAX_NODES];

int idx = 0;
int new_node(ll l, ll r) {
  nodes[idx].l = l, nodes[idx].r = r;
  return idx++;
}

void push_down(int idx) {
  Node &u = nodes[idx];
  if (!u.lazy)
    return;

  u.val = u.r - u.l + 1;
  if (u.l == u.r)
    return;

  ll mid = (u.l + u.r) / 2;
  if (u.l_idx == -1)
    u.l_idx = new_node(u.l, mid);
  if (u.r_idx == -1)
    u.r_idx = new_node(mid + 1, u.r);

  nodes[u.l_idx].lazy = nodes[u.r_idx].lazy = 1;
}

ll query(int idx, ll ql, ll qr) {
  Node &u = nodes[idx];
  push_down(idx);

  if (u.l > qr || ql > u.r)
    return 0;
  if (ql <= u.l && u.r <= qr)
    return u.val;

  ll mid = (u.l + u.r) / 2;
  if (u.l_idx == -1)
    u.l_idx = new_node(u.l, mid);
  if (u.r_idx == -1)
    u.r_idx = new_node(mid + 1, u.r);

  return query(u.l_idx, ql, qr) + query(u.r_idx, ql, qr);
}

void upd(int idx, ll ql, ll qr) {
  Node &u = nodes[idx];
  push_down(idx);

  if (u.l > qr || ql > u.r)
    return;
  if (ql <= u.l && u.r <= qr) {
    u.lazy = 1;
    push_down(idx);
    return;
  }

  ll mid = (u.l + u.r) / 2;
  if (u.l_idx == -1)
    u.l_idx = new_node(u.l, mid);
  if (u.r_idx == -1)
    u.r_idx = new_node(mid + 1, u.r);

  upd(u.l_idx, ql, qr), upd(u.r_idx, ql, qr);

  u.val = nodes[u.l_idx].val + nodes[u.r_idx].val;
}

void solve() {
  int root = new_node(0, INF);
  ll c = 0;
  int m;
  cin >> m;
  while (m--) {
    ll t, x, y;
    cin >> t >> x >> y;
    x += c, y += c;
    if (t == 1)
      cout << (c = query(root, x, y)) << "\n";
    else
      upd(root, x, y);
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  clock_t start = clock();

  int test_cases = 1;
  // cin >> test_cases;

  while (test_cases--)
    solve();

#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:185:11: warning: unused variable 'start' [-Wunused-variable]
  185 |   clock_t start = clock();
      |           ^~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	137164 KB	Output is correct
2	Correct	49 ms	137184 KB	Output is correct
3	Correct	50 ms	137220 KB	Output is correct
4	Correct	62 ms	137292 KB	Output is correct
5	Correct	69 ms	137316 KB	Output is correct
6	Correct	72 ms	137292 KB	Output is correct
7	Correct	66 ms	137284 KB	Output is correct
8	Correct	149 ms	137396 KB	Output is correct
9	Correct	248 ms	137548 KB	Output is correct
10	Correct	266 ms	137608 KB	Output is correct
11	Correct	260 ms	137576 KB	Output is correct
12	Correct	276 ms	137672 KB	Output is correct
13	Runtime error	254 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-