답안 #822970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
822970 2023-08-12T06:16:16 Z arush_agu 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
251 ms 169160 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 + 5;
const ld EPS = 1e-9;

const int MAX_NODES = 1e5 * 35;

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;
  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;

  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);

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

int query(int idx, int ql, int 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;

  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);

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

void upd(int idx, int ql, int 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;
  }

  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:185:11: warning: unused variable 'start' [-Wunused-variable]
  185 |   clock_t start = clock();
      |           ^~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 82380 KB Output is correct
2 Correct 34 ms 82396 KB Output is correct
3 Correct 33 ms 82460 KB Output is correct
4 Correct 44 ms 82448 KB Output is correct
5 Correct 55 ms 82512 KB Output is correct
6 Correct 44 ms 82424 KB Output is correct
7 Correct 45 ms 82516 KB Output is correct
8 Correct 137 ms 82760 KB Output is correct
9 Correct 226 ms 82824 KB Output is correct
10 Correct 251 ms 82872 KB Output is correct
11 Correct 248 ms 82960 KB Output is correct
12 Correct 245 ms 82964 KB Output is correct
13 Runtime error 224 ms 169160 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -