Submission #778065

#	Time	Username	Problem	Language	Result	Execution time	Memory
778065		LCPlayer	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2 ms	1236 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

template <class T>
struct TreeNode {
  T value;
  bool lazy = false;
  T lazyValue = 0;
  array<int, 2> children = {0, 0};
};

vector<TreeNode<ll>> st;
int createTreeNode() { // returns the index
  st.emplace_back();
  return st.size() - 1;
}

template <class T>
class SparseSegmentTree {
public:
  SparseSegmentTree(int n) : n(n) { build(); }
  // Range update [i, j] to val.
  void update(int i, int j, T val) { root = 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; 
  int root;
  void build() {
    root = createTreeNode();
  }
  int leftChild(int index) {
    // dynamic allocate child node
    if (!st[index].children[0]) { st[index].children[0] = createTreeNode(); }
    return st[index].children[0]; 
  }
  int rightChild(int index) { 
    // dynamic allocate child node
    if (!st[index].children[1]) { st[index].children[1] = createTreeNode(); }
    return st[index].children[1]; 
  }
  T calculate(T v1, T v2) {
    return v1 + v2; // case by case 1/4.
  }
  // propagate lazy value one level down.
  void propagate(int index, int L, int R) {
    if (!st[index].lazy) return;
    if (L == R) {
      // case by case 2/4.
      // data[L] += st[index].lazyValue; // leaf node; time to update.
    } else {
      int lc = leftChild(index); int rc = rightChild(index); int m = (L + R) / 2;
      st[lc].lazy = st[rc].lazy = true;
      // case by case 3/4.
      st[lc].lazyValue = st[index].lazyValue;
      st[rc].lazyValue = st[index].lazyValue;
      st[lc].value = (m - L + 1) * st[index].lazyValue;
      st[rc].value = (R - (m + 1) + 1) * st[index].lazyValue;
    }
    st[index].lazy = false; st[index].lazyValue = 0;
  }
  
  int update(int index, int L, int R, int i, int j, T val) {
    assert(L <= i && i <= j && j <= R);
    propagate(index, L, R);
    if (i == L && j == R) {
      // case by case 4/4.
      int newIndex = createTreeNode();
      // st[newIndex] = st[index]; // No copy, as children should not be re-used.
      st[newIndex].lazyValue = val; st[newIndex].value = (R - L + 1) * val;
      st[newIndex].lazy = true;
      return newIndex;
    }
    int m = (L + R) / 2; 
    int lc = leftChild(index); int rc = rightChild(index);
    int newIndex = createTreeNode();
    st[newIndex] = st[index]; // copy first to re-use some non-updated child in the following
    if (i <= m) { 
      st[newIndex].children[0] = lc = update(lc, L, m, i, min(m, j), val);
    }
    if (j >= m + 1) {
      st[newIndex].children[1] = rc = update(rc, m + 1, R, max(i, m + 1), j, val);
    }
    T lValue = st[lc].value; T rValue = st[rc].value;
    st[newIndex].value = calculate(lValue, rValue);
    return newIndex;
  }
  
  T query(int index, int L, int R, int i, int j) {
    assert(L <= i && i <= j && j <= R);
    T ans;
    if (i == L && j == R) { 
      ans = st[index].value;
    } else {
      propagate(index, L, R); int m = (L + R) / 2;
      int lc = leftChild(index); int rc = rightChild(index);
      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:129:3: note: in expansion of macro 'debug'
  129 |   debug(n);
      |   ^~~~~

• Subtask 1: 0 / 100