Submission #780780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
780780	2023-07-12T13:02:21 Z	LCPlayer	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	382 ms	262144 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);
    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);
      |   ^~~~~

Subtask #1

0 / 100.0

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