답안 #822985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
822985 2023-08-12T06:32:12 Z arush_agu 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
252 ms 190856 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 = 2e5 + 5;

struct Node {
  int val, lazy, l, r;
  Node() : val(0), lazy(0), l(-1), r(-1){};
};

struct ST {
  vector<Node> f;
  int n;

  ST() : f(MAX * 60), n(1){};

  void push(int x, int l, int r) {
    if (!f[x].lazy)
      return;
    if (f[x].l == -1)
      f[x].l = ++n;
    if (f[x].r == -1)
      f[x].r = ++n;

    int m = (l + r) / 2;
    f[f[x].l].lazy = f[x].lazy;
    f[f[x].r].lazy = f[x].lazy;
    f[f[x].l].val = f[x].lazy * (m - l + 1);
    f[f[x].r].val = f[x].lazy * (r - m);
    f[x].lazy = 0;
  }

  void upd(int u, int v, int val, int x = 1, int l = 1, int r = INF) {
    if (l > v || r < u)
      return;
    if (u <= l && r <= v) {
      f[x].val = val * (r - l + 1);
      f[x].lazy = val;
      return;
    }

    if (f[x].l == -1)
      f[x].l = ++n;
    if (f[x].r == -1)
      f[x].r = ++n;
    push(x, l, r);

    int m = (l + r) >> 1;
    upd(u, v, val, f[x].l, l, m);
    upd(u, v, val, f[x].r, m + 1, r);
    f[x].val = f[f[x].l].val + f[f[x].r].val;
  }

  int query(int u, int v, int x = 1, int l = 1, int r = INF) {
    if (l > v || r < u)
      return 0;
    if (u <= l && r <= v)
      return f[x].val;

    if (f[x].l == -1)
      f[x].l = ++n;
    if (f[x].r == -1)
      f[x].r = ++n;
    push(x, l, r);

    int m = (l + r) >> 1;
    int ql = query(u, v, f[x].l, l, m);
    int qr = query(u, v, f[x].r, m + 1, r);
    return (ql + qr);
  }
};

void solve() {
  int q;
  ST st;
  cin >> q;
  int c = 0;
  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1)
      cout << (c = st.query(x + c, y + c)) << "\n";
    else
      st.upd(x + c, y + c, 1);
  }
}

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:180:11: warning: unused variable 'start' [-Wunused-variable]
  180 |   clock_t start = clock();
      |           ^~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 188080 KB Output is correct
2 Correct 73 ms 188128 KB Output is correct
3 Correct 79 ms 188068 KB Output is correct
4 Correct 79 ms 188188 KB Output is correct
5 Correct 87 ms 188208 KB Output is correct
6 Correct 80 ms 188220 KB Output is correct
7 Correct 82 ms 188160 KB Output is correct
8 Correct 122 ms 188284 KB Output is correct
9 Correct 199 ms 188464 KB Output is correct
10 Correct 229 ms 188568 KB Output is correct
11 Correct 189 ms 188548 KB Output is correct
12 Correct 199 ms 188524 KB Output is correct
13 Correct 184 ms 188620 KB Output is correct
14 Correct 176 ms 188684 KB Output is correct
15 Correct 219 ms 189548 KB Output is correct
16 Correct 252 ms 190856 KB Output is correct
17 Correct 180 ms 190668 KB Output is correct
18 Correct 182 ms 190712 KB Output is correct
19 Correct 230 ms 190848 KB Output is correct
20 Correct 222 ms 190816 KB Output is correct