Submission #777335

#TimeUsernameProblemLanguageResultExecution timeMemory
777335LCPlayer원숭이와 사과 나무 (IZhO12_apple)C++14
0 / 100
451 ms262144 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...