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
#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();
      |           ^~~~~
# 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 -