Submission #822947

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
822947	2023-08-12T05:53:48 Z	arush_agu	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	380 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;

struct SegNode {
  ll l, r, mid, val;
  SegNode *left, *right;
  bool lazy = 0;

  SegNode(ll l, ll r)
      : l(l), r(r), mid((l + r) / 2), left(nullptr), right(nullptr) {}

  void push_down() {
    if (!lazy)
      return;
    val = (r - l + 1);
    if (l == r)
      return;

    if (!left)
      left = new SegNode(l, mid);
    if (!right)
      right = new SegNode(mid + 1, r);

    left->lazy = right->lazy = 1;
  }

  ll query(ll ql, ll qr) {
    push_down();

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

    if (!left)
      left = new SegNode(l, mid);
    if (!right)
      right = new SegNode(mid + 1, r);

    return left->query(ql, qr) + right->query(ql, qr);
  }

  void upd(ll ql, ll qr) {
    push_down();

    if (l > qr || ql > r)
      return;

    if (ql <= l && r <= qr) {
      lazy = 1;
      push_down();
      return;
    }

    if (!left)
      left = new SegNode(l, mid);
    if (!right)
      right = new SegNode(mid + 1, r);

    left->upd(ql, qr);
    right->upd(ql, qr);

    val = left->val + right->val;
  }

  void print() {
    push_down();
    cerr << "L: " << l << " R: " << r << " Val: " << val << "\n";
    if (left)
      left->print();
    if (right)
      right->print();
  }
};

void solve() {
  SegNode *root = new SegNode(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 = root->query(x, y)) << "\n";
    else
      root->upd(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	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	19 ms	11484 KB	Output is correct
5	Correct	20 ms	13780 KB	Output is correct
6	Correct	22 ms	13396 KB	Output is correct
7	Correct	18 ms	13780 KB	Output is correct
8	Correct	152 ms	103288 KB	Output is correct
9	Correct	328 ms	176052 KB	Output is correct
10	Correct	353 ms	197496 KB	Output is correct
11	Correct	350 ms	214092 KB	Output is correct
12	Correct	380 ms	221260 KB	Output is correct
13	Runtime error	344 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-