Submission #822979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
822979	2023-08-12T06:24:17 Z	arush_agu	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	244 ms	216244 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 + 5;
const ld EPS = 1e-9;

const int MAX_NODES = 1e5 * 45;

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

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

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

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

  int mid = ((ll)u.l + (ll)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;
}

int query(int idx, int ql, int qr) {
  assert(idx >= 0);
  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;

  int mid = ((ll)u.l + (ll)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, int ql, int qr) {
  assert(idx >= 0);
  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;
  }

  int 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);
  int c = 0;
  int m;
  cin >> m;
  while (m--) {
    int 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:189:11: warning: unused variable 'start' [-Wunused-variable]
  189 |   clock_t start = clock();
      |           ^~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	105948 KB	Output is correct
2	Correct	43 ms	105932 KB	Output is correct
3	Correct	45 ms	105888 KB	Output is correct
4	Correct	52 ms	105932 KB	Output is correct
5	Correct	54 ms	105996 KB	Output is correct
6	Correct	55 ms	105932 KB	Output is correct
7	Correct	54 ms	105936 KB	Output is correct
8	Correct	133 ms	106072 KB	Output is correct
9	Correct	222 ms	106316 KB	Output is correct
10	Correct	242 ms	106260 KB	Output is correct
11	Correct	244 ms	106336 KB	Output is correct
12	Correct	233 ms	106308 KB	Output is correct
13	Correct	227 ms	106676 KB	Output is correct
14	Correct	240 ms	108520 KB	Output is correct
15	Runtime error	238 ms	216244 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-