답안 #479970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
479970 2021-10-14T03:48:22 Z cs142857 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
316 ms 98452 KB
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <array>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <memory>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#ifdef DBG
  #define dbg 1
  #define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
  #define dbg 0
  #define dpf(...) 42
#endif
 
#define SIZE(c) int((c).size())
#define REP(i,c) for(auto &i : (c))
#define ALL(c) (c).begin(),(c).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PI;

template <typename T> inline void UpdateMax(T& x, T v) { x = max(x, v); }
template <typename T> inline void UpdateMin(T& x, T v) { x = min(x, v); }

template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;

// Dynamic Segment Tree base class.
class SegTree {
 public:
  struct Node {
    int l = -1, r = -1;
    int sum = 0;
    char set = 0;
  };
  vector<Node> a;
  int max_idx;

  using T = Node;

  SegTree() {}
  inline virtual void CombineNode(const T& lv, const T& rv, T& v) {
    v.sum = lv.sum + rv.sum;
  }

  void Init(int max_idx, int init_max_update = 0) {
    assert(max_idx >= -1);
    this->max_idx = max_idx;
    int m = max_idx + 1;
    int c = 1;
    while (m) {
      ++c;
      m >>= 1;
    }
    a.resize(1);
    a[0] = Node();
    a.reserve(1 + c * init_max_update);
  }

  void RangeSet(int l, int r) { RangeSet(l, r, 0, max_idx, 0); }

  int QuerySum(int l, int r) { return QuerySum(l, r, 0, max_idx, 0); }

  void Debug() {
    if (!dbg) return;
    for(int i=0;i<SIZE(a);++i) {
      dpf("%d: %d %d, %d %d\n", i, a[i].sum, a[i].set, a[i].l, a[i].r);
    }
  }

 protected:
  inline void ApplySet(int l,int r,int p) {
    a[p].sum = r - l + 1;
    a[p].set = 1;
  }

  // Update p's children's lazy tags.
  virtual void PushDown(int l, int r, int p) {
    if (a[p].l < 0) {
      a[p].l = SIZE(a);
      a.emplace_back();
    }
    if (a[p].r < 0) {
      a[p].r = SIZE(a);
      a.emplace_back();
    }
    int m = (l + r) >> 1;
    if (a[p].set) {
      ApplySet(l, m, a[p].l);
      ApplySet(m + 1, r, a[p].r);
      a[p].set = 0;
    }
  }

  // Combines left and right children to current node.
  inline void PushUp(int p) { CombineNode(a[a[p].l], a[a[p].r], a[p]); }

 private:
  void RangeSet(int ql, int qr, int l, int r, int p) {
    dpf("RangeSet: %d %d, %d %d %d\n",ql,qr,l,r,p);
    if (ql > r || qr < l) return;
    if (ql <= l && qr >= r) {
      ApplySet(l, r, p);
      return;
    }
    PushDown(l, r, p);
    int m = (l + r) >> 1;
    RangeSet(ql, qr, l, m, a[p].l);
    RangeSet(ql, qr, m + 1, r, a[p].r);
    PushUp(p);
  }

  int QuerySum(int ql, int qr, int l, int r, int p) {
    if (ql > r || qr < l) return 0;
    if (ql <= l && qr >= r) return a[p].sum;
    PushDown(l, r, p);
    int m = (l + r) >> 1;
    int res =
        QuerySum(ql, qr, l, m, a[p].l) + QuerySum(ql, qr, m + 1, r, a[p].r);
    PushUp(p);
    return res;
  }
};

SegTree st;

int Query(int l, int r) { return st.QuerySum(l, r); }

void Update(int l, int r) { st.RangeSet(l, r); }

void Solve() {
  int nq;
  scanf("%d",&nq);
  st.Init(1000000000, nq);

  int C = 0;
  while(nq--) {
    int t,l,r;
    scanf("%d%d%d",&t,&l,&r);
    dpf("Query %d %d %d\n", t, l, r);
    l += C, r += C;
    if(t==1) {
      C = Query(l, r);
      printf("%d\n", C);
    } else {
      Update(l, r);
    }
    st.Debug();
  }
}

int main() {
  int t = 1;
  // scanf("%d", &t);
  for (int i = 1; i <= t; ++i) {
    Solve();
  }

  return 0;
}

Compilation message

apple.cpp: In member function 'void SegTree::Debug()':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
   32 |   #define dpf(...) 42
      |                    ^~
apple.cpp:95:7: note: in expansion of macro 'dpf'
   95 |       dpf("%d: %d %d, %d %d\n", i, a[i].sum, a[i].set, a[i].l, a[i].r);
      |       ^~~
apple.cpp: In member function 'void SegTree::RangeSet(int, int, int, int, int)':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
   32 |   #define dpf(...) 42
      |                    ^~
apple.cpp:128:5: note: in expansion of macro 'dpf'
  128 |     dpf("RangeSet: %d %d, %d %d %d\n",ql,qr,l,r,p);
      |     ^~~
apple.cpp: In function 'void Solve()':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
   32 |   #define dpf(...) 42
      |                    ^~
apple.cpp:168:5: note: in expansion of macro 'dpf'
  168 |     dpf("Query %d %d %d\n", t, l, r);
      |     ^~~
apple.cpp:161:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |   scanf("%d",&nq);
      |   ~~~~~^~~~~~~~~~
apple.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     scanf("%d%d%d",&t,&l,&r);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 13 ms 1860 KB Output is correct
5 Correct 14 ms 2344 KB Output is correct
6 Correct 15 ms 2252 KB Output is correct
7 Correct 15 ms 2300 KB Output is correct
8 Correct 102 ms 15560 KB Output is correct
9 Correct 217 ms 26364 KB Output is correct
10 Correct 220 ms 29132 KB Output is correct
11 Correct 217 ms 31116 KB Output is correct
12 Correct 204 ms 32116 KB Output is correct
13 Correct 206 ms 37312 KB Output is correct
14 Correct 245 ms 37560 KB Output is correct
15 Correct 292 ms 98380 KB Output is correct
16 Correct 316 ms 98452 KB Output is correct
17 Correct 193 ms 38844 KB Output is correct
18 Correct 204 ms 38792 KB Output is correct
19 Correct 313 ms 98256 KB Output is correct
20 Correct 306 ms 98328 KB Output is correct