답안 #777719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777719	2023-07-09T13:56:17 Z	LCPlayer	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	277 ms	166888 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;
  array<int, 2> 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;
  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:117:3: note: in expansion of macro 'debug'
  117 |   debug(n);
      |   ^~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	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	11 ms	3144 KB	Output is correct
5	Correct	11 ms	5740 KB	Output is correct
6	Correct	11 ms	5760 KB	Output is correct
7	Correct	11 ms	5748 KB	Output is correct
8	Correct	81 ms	42416 KB	Output is correct
9	Correct	167 ms	42444 KB	Output is correct
10	Correct	181 ms	84572 KB	Output is correct
11	Correct	190 ms	84572 KB	Output is correct
12	Correct	193 ms	84432 KB	Output is correct
13	Correct	169 ms	84444 KB	Output is correct
14	Correct	170 ms	84464 KB	Output is correct
15	Correct	275 ms	166808 KB	Output is correct
16	Correct	276 ms	166888 KB	Output is correct
17	Correct	174 ms	84424 KB	Output is correct
18	Correct	186 ms	84624 KB	Output is correct
19	Correct	267 ms	166792 KB	Output is correct
20	Correct	277 ms	166656 KB	Output is correct