Submission #780782

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
780782	2023-07-12T13:05:15 Z	LCPlayer	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	458 ms	260400 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 {
  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);
    T ans;
    if (i == L && j == R) { 
      ans = curr->value;
    } else {
      expand(curr);
      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);
      |   ^~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	15 ms	5972 KB	Output is correct
5	Correct	13 ms	7320 KB	Output is correct
6	Correct	13 ms	7088 KB	Output is correct
7	Correct	13 ms	7208 KB	Output is correct
8	Correct	145 ms	55176 KB	Output is correct
9	Correct	247 ms	96020 KB	Output is correct
10	Correct	249 ms	106188 KB	Output is correct
11	Correct	263 ms	113928 KB	Output is correct
12	Correct	279 ms	117484 KB	Output is correct
13	Correct	231 ms	135116 KB	Output is correct
14	Correct	230 ms	136952 KB	Output is correct
15	Correct	408 ms	253176 KB	Output is correct
16	Correct	402 ms	254772 KB	Output is correct
17	Correct	236 ms	143964 KB	Output is correct
18	Correct	235 ms	143740 KB	Output is correct
19	Correct	398 ms	260272 KB	Output is correct
20	Correct	458 ms	260400 KB	Output is correct