답안 #780780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780780 2023-07-12T13:02:21 Z LCPlayer 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
382 ms 262144 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);
    expand(curr);
    T ans;
    if (i == L && j == R) { 
      ans = curr->value;
    } else {
      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 1 ms 212 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 18 ms 7252 KB Output is correct
5 Correct 19 ms 8892 KB Output is correct
6 Correct 14 ms 8528 KB Output is correct
7 Correct 20 ms 8916 KB Output is correct
8 Correct 160 ms 66892 KB Output is correct
9 Correct 298 ms 116304 KB Output is correct
10 Correct 331 ms 128432 KB Output is correct
11 Correct 318 ms 137756 KB Output is correct
12 Correct 336 ms 141968 KB Output is correct
13 Correct 282 ms 164300 KB Output is correct
14 Correct 273 ms 165892 KB Output is correct
15 Runtime error 382 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -