답안 #780799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780799 2023-07-12T13:18:09 Z LCPlayer 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
525 ms 258328 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 {
  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, 0, n - 1, i, j, val); }
  // Range query [i, j].
  T query(int i, int j) { return query(root, 0, n - 1, i, j); }
  void clear() { clear(root); }
private:
  int n; 
  TreeNode<T>* root;
  TreeNode<T>* build() {
    return new TreeNode<T>();
  }
  void expand(TreeNode<T>* curr, int L, int R) {
    if (!curr->leftChild) { curr->leftChild = new TreeNode<T>(); }
    if (!curr->rightChild) { curr->rightChild = new TreeNode<T>(); }
  }
  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, int L, int R) {
    if (!curr->lazy) return;
    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 L, int R, int i, int j, T val) {
    assert(L <= i && i <= j && j <= R);
    expand(curr, L, R);
    propagate(curr, L, R);
    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, L, m, i, min(m, j), val); }
    if (j >= m + 1) { update(rc, m + 1, R, 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 L, int R, int i, int j) {
    assert(L <= i && i <= j && j <= R);
    T ans;
    if (i == L && j == R) { 
      ans = curr->value;
    } else {
      expand(curr, L, R);
      propagate(curr, L, R); int m = (L + R) / 2;
      TreeNode<T> *lc = curr->leftChild, *rc = curr->rightChild;
      if (j <= m) { ans = query(lc, L, m, i, j);
      } else if (i >= m + 1) { ans = query(rc, m + 1, R, i, j);
      } else {
        T lValue = query(lc, L, m, i, m);
        T rValue = query(rc, m + 1, R, m + 1, j);
        ans = calculate(lValue, rValue);
      }
    }
    return ans;
  }
  
  void clear(TreeNode<T>* curr) {
    if (curr->leftChild) {
      clear(curr->leftChild);
      delete curr->leftChild;
      curr->leftChild = NULL;
    }
    if (curr->rightChild) {
      clear(curr->rightChild);
      delete curr->rightChild;
      curr->rightChild = NULL;
    }
  }
};
 
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);
    }
  }
  st.clear();
}
 
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:125:3: note: in expansion of macro 'debug'
  125 |   debug(n);
      |   ^~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 12 ms 6020 KB Output is correct
5 Correct 16 ms 7304 KB Output is correct
6 Correct 15 ms 7148 KB Output is correct
7 Correct 16 ms 7252 KB Output is correct
8 Correct 155 ms 55288 KB Output is correct
9 Correct 329 ms 95932 KB Output is correct
10 Correct 309 ms 106204 KB Output is correct
11 Correct 323 ms 113868 KB Output is correct
12 Correct 326 ms 117388 KB Output is correct
13 Correct 307 ms 135204 KB Output is correct
14 Correct 325 ms 136872 KB Output is correct
15 Correct 524 ms 250940 KB Output is correct
16 Correct 525 ms 252572 KB Output is correct
17 Correct 320 ms 141808 KB Output is correct
18 Correct 305 ms 141644 KB Output is correct
19 Correct 520 ms 258328 KB Output is correct
20 Correct 519 ms 258232 KB Output is correct