제출 #479970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479970		cs142857	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	316 ms	98452 KiB

apple

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

컴파일 시 표준 에러 (stderr) 메시지

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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100