Submission #777335

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
777335	2023-07-09T06:01:34 Z	LCPlayer	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	451 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

template <class T>
struct TreeNode {
  T value;
  bool lazy = false;
  T lazyValue = 0;
  vector<int> children = {0, 0};
};
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) { update(0, 0, n-1, i, j, val); }
  // Range query [i, j].
  T query(int i, int j) { return query(0, 0, n-1, i, j); }

private:
  int n; 
  vector<TreeNode<T>> st;
  int leftChild(int index) { 
    if (!st[index].children[0]) {
      st.emplace_back();
      st[index].children[0] = st.size() - 1;
    }
    return st[index].children[0]; 
  }
  int rightChild(int index) { 
    if (!st[index].children[1]) {
      st.emplace_back();
      st[index].children[1] = st.size() - 1;
    }
    return st[index].children[1]; 
  }
  T calculate(T v1, T v2) {
    return v1 + v2; // case by case 1/4.
  }
  void build() {
    st.emplace_back();
  }

  // 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;
  }
  
  void 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.
      st[index].lazyValue = val; st[index].value = (R - L + 1) * val;
      st[index].lazy = true; return;
    }
    int m = (L + R) / 2; 
    int lc = leftChild(index); int rc = rightChild(index);
    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 = st[lc].value; T rValue = st[rc].value;
    st[index].value = calculate(lValue, rValue);
  }

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

Subtask #1

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	1 ms	212 KB	Output is correct
4	Correct	20 ms	8652 KB	Output is correct
5	Correct	27 ms	14808 KB	Output is correct
6	Correct	22 ms	14772 KB	Output is correct
7	Correct	20 ms	14808 KB	Output is correct
8	Correct	190 ms	116200 KB	Output is correct
9	Correct	380 ms	137904 KB	Output is correct
10	Correct	446 ms	232220 KB	Output is correct
11	Correct	451 ms	232228 KB	Output is correct
12	Correct	445 ms	232020 KB	Output is correct
13	Correct	386 ms	232152 KB	Output is correct
14	Correct	387 ms	232128 KB	Output is correct
15	Runtime error	438 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-