Submission #780799

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
780799	2023-07-12T13:18:09 Z	LCPlayer	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	525 ms	258328 KB

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); }
  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);
      |   ^~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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