Submission #780787

#	Time	Username	Problem	Language	Result	Execution time	Memory
780787		LCPlayer	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	428 ms	258264 KiB

apple

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

private:
  int n; 
  TreeNode<T>* root;
  TreeNode<T>* build() {
    return new TreeNode<T>();
  }
  void expand(TreeNode<T>* curr, int L, int R) {
    int m = (L + R) / 2;
    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 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 (stderr)

apple.cpp: In function 'void solve()':
apple.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 88
      |                    ^~
apple.cpp:113:3: note: in expansion of macro 'debug'
  113 |   debug(n);
      |   ^~~~~
apple.cpp: In instantiation of 'void SparseSegmentTree<T>::expand(TreeNode<T>*, int, int) [with T = int]':
apple.cpp:95:7:   required from 'T SparseSegmentTree<T>::query(TreeNode<T>*, int, int, int, int) [with T = int]'
apple.cpp:37:39:   required from 'T SparseSegmentTree<T>::query(int, int) [with T = int]'
apple.cpp:124:29:   required from here
apple.cpp:46:9: warning: unused variable 'm' [-Wunused-variable]
   46 |     int m = (L + R) / 2;
      |         ^

• Subtask 1: 100 / 100