답안 #780782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780782 2023-07-12T13:05:15 Z LCPlayer 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
458 ms 260400 KB
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 88
#define dout if (0) cout
#endif
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (int i=0;i<a.size();i++) cin>>a[i]; return cin; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define RE(i, n) for (int i = 0; i < n; i++)
#define RE2(i, start, n) for (int i = start; i < n; i++)
 
// #define MULTI_CASES
// #define LOCAL_MULTI_CASES

// SparseSegmentTree (Dynamic SegmentTree), with lazy propagate.
// Similar to above, only with dynamic allocate space for children nodes.
template <class T>
struct TreeNode {
  int l, r;
  T value = 0;
  bool lazy = false;
  T lazyValue = 0;
  TreeNode *leftChild = NULL, *rightChild = NULL;
};
template <class T>
class SparseSegmentTree {
public:
  // n is the max value bound (exclusive), allowed range is [0, n - 1].
  SparseSegmentTree(int n) : n(n) { root = build(); }
  // Range update [i, j] to val.
  void update(int i, int j, T val) { update(root, i, j, val); }
  // Range query [i, j].
  T query(int i, int j) { return query(root, i, j); }

private:
  int n; 
  TreeNode<T>* root;
  TreeNode<T>* createNewTreeNode(int l, int r) {
    TreeNode<T>* ret = new TreeNode<T>(); ret->l = l; ret->r = r; return ret;
  }
  TreeNode<T>* build() {
    return createNewTreeNode(0, n - 1);
  }
  void expand(TreeNode<T>* curr) {
    int m = (curr->l + curr->r) / 2;
    if (!curr->leftChild) { curr->leftChild = createNewTreeNode(curr->l, m); }
    if (!curr->rightChild) { curr->rightChild = createNewTreeNode(m + 1, curr->r); }
  }
  T calculate(T v1, T v2) {
    return v1 + v2; // case by case 1/4.
  }
  // propagate lazy value one level down.
  void propagate(TreeNode<T>* curr) {
    if (!curr->lazy) return;
    int L = curr->l, R = curr->r;
    if (L == R) {
      // case by case 2/4.
      // data[L] += curr->lazyValue; // leaf node; time to update.
    } else {
      TreeNode<T> *lc = curr->leftChild, *rc = curr->rightChild; int m = (L + R) / 2;
      lc->lazy = rc->lazy = true;
      // case by case 3/4.
      lc->lazyValue = curr->lazyValue;
      rc->lazyValue = curr->lazyValue;
      lc->value = (m - L + 1) * curr->lazyValue;
      rc->value = (R - (m + 1) + 1) * curr->lazyValue;
    }
    curr->lazy = false; curr->lazyValue = 0;
  }

  void update(TreeNode<T>* curr, int i, int j, T val) {
    int L = curr->l, R = curr->r;
    assert(L <= i && i <= j && j <= R);
    expand(curr);
    propagate(curr);
    if (i == L && j == R) {
      // case by case 4/4.
      curr->lazyValue = val;
      curr->value = (R - L + 1) * val;
      curr->lazy = true; return;
    }
    int m = (L + R) / 2; 
    TreeNode<T> *lc = curr->leftChild, *rc = curr->rightChild;
    if (i <= m) { update(lc, i, min(m, j), val); }
    if (j >= m + 1) { update(rc, max(i, m + 1), j, val); }
    T lValue = lc->value; T rValue = rc->value;
    curr->value = calculate(lValue, rValue);
  }

  T query(TreeNode<T>* curr, int i, int j) {
    int L = curr->l, R = curr->r;
    assert(L <= i && i <= j && j <= R);
    T ans;
    if (i == L && j == R) { 
      ans = curr->value;
    } else {
      expand(curr);
      propagate(curr); int m = (L + R) / 2;
      TreeNode<T> *lc = curr->leftChild, *rc = curr->rightChild;
      if (j <= m) { ans = query(lc, i, j);
      } else if (i >= m + 1) { ans = query(rc, i, j);
      } else {
        T lValue = query(lc, i, m);
        T rValue = query(rc, m + 1, j);
        ans = calculate(lValue, rValue);
      }
    }
    return ans;
  }
};
 
void solve() {
  int n;
  cin >> n;
  debug(n);
  int preans = 0;
  SparseSegmentTree<int> st(1000000000);
  RE(i, n) {
    int type, x, y;
    cin >> type >> x >> y;    
    x += preans; y += preans;
    x--; y--;
    
    if (type == 1) {
      // query
      preans = st.query(x, y);
      cout << preans << "\n";
    } else {
      assert(type == 2);
      // update
      st.update(x, y, 1);
    }
  }
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int cases = 1;
  #if defined MULTI_CASES || (defined LOCAL && defined LOCAL_MULTI_CASES)
  cin >> cases;
  #endif
  for (int i = 0; i < cases; i++) {
    dout << "cases: " << i + 1 << endl;
    solve();
    dout << endl;
  }
  
  return 0;
}

Compilation message

apple.cpp: In function 'void solve()':
apple.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 88
      |                    ^~
apple.cpp:120:3: note: in expansion of macro 'debug'
  120 |   debug(n);
      |   ^~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 15 ms 5972 KB Output is correct
5 Correct 13 ms 7320 KB Output is correct
6 Correct 13 ms 7088 KB Output is correct
7 Correct 13 ms 7208 KB Output is correct
8 Correct 145 ms 55176 KB Output is correct
9 Correct 247 ms 96020 KB Output is correct
10 Correct 249 ms 106188 KB Output is correct
11 Correct 263 ms 113928 KB Output is correct
12 Correct 279 ms 117484 KB Output is correct
13 Correct 231 ms 135116 KB Output is correct
14 Correct 230 ms 136952 KB Output is correct
15 Correct 408 ms 253176 KB Output is correct
16 Correct 402 ms 254772 KB Output is correct
17 Correct 236 ms 143964 KB Output is correct
18 Correct 235 ms 143740 KB Output is correct
19 Correct 398 ms 260272 KB Output is correct
20 Correct 458 ms 260400 KB Output is correct