제출 #479880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479880		cs142857	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	47 ms	1152 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>>;

// Splay Tree base class.
// Works like map<K, V>, do not allow duplicate key.
template <typename K, typename V>
class BaseSplayTree {
 public:
  struct Node {
    K k;
    V v;
    int p = 0;  // parent
    int ch[2] = {0,0};  // child
  };
  vector<Node> a;

  BaseSplayTree(int init_capacity = 0) { Reset(init_capacity); }

  void Reset(int init_capacity = 0) {
    a.resize(1);
    a[0] = null_node();
    a.reserve(init_capacity + 1);
    empty_idx.clear();
  }

  inline int Side(int u) { return a[a[u].p].ch[1] == u; }

  int Splay(int u) {
    assert(u > 0);
    while (1) {
      int pu = a[u].p;
      if (!pu) break;
      int ppu = a[pu].p;
      if(ppu) {
        if(Side(pu) == Side(u)) {
          Rotate(pu);
        } else {
          Rotate(u);
        }
      }
      Rotate(u);
    }
    return u;
  }

  // Returns u that a[u].k == k, or 0 not found.
  int Find(int& root, K k) {
    int u = root;
    while (u) {
      if (a[u].k == k) {
        return root = Splay(u);
      }
      if(a[u].k > k) {
        u = a[u].ch[0];
      } else {
        u = a[u].ch[1];
      }
    }
    return 0;
  }

  // Returns u that a[u].k is min.
  int FindMin(int& root) {
    if (!root) return 0;
    int u=root;
    while (a[u].ch[0]) u = a[u].ch[0];
    return root = Splay(u);
  }

  // Returns u that a[u].k is max.
  int FindMax(int& root) {
    if (!root) return 0;
    int u = root;
    while (a[u].ch[1]) u = a[u].ch[1];
    return root = Splay(u);
  }

  // Gets the prev node of root, or 0 if not present.
  int Prev(int& root) {
    int u = a[root].ch[0];
    while (a[u].ch[1]) u = a[u].ch[1];
    if (u) root = Splay(u);
    return u;
  }

  // Gets the next node of root, or 0 if not present.
  int Next(int& root) {
    int u = a[root].ch[1];
    while (a[u].ch[0]) u = a[u].ch[0];
    if (u) root = Splay(u);
    return u;
  }

  // Returns u that a[u].k is maximal and < k, or 0 not found.
  int Prev(int& root, K k) {
    bool insert_res = Insert(root, k);
    int u = a[root].ch[0];
    while (a[u].ch[1]) u = a[u].ch[1];
    if (insert_res) assert(Delete(root, k));
    if (u) root = Splay(u);
    return u;
  }

  // Returns u that a[u].k is minimal and > k, or 0 not found.
  int Next(int& root, K k) {
    bool insert_res = Insert(root, k);
    int u = a[root].ch[1];
    while (a[u].ch[0]) u = a[u].ch[0];
    if (insert_res) assert(Delete(root, k));
    if (u) root = Splay(u);
    return u;
  }

  // Returns false if the key already exists.
  bool Insert(int& root, K k) {
    int u = root;
    int side = 0;
    if (root) {
      while (1) {
        if (k == a[u].k) {
          root = Splay(u);
          return 0;
        }
        if (k < a[u].k) side=0; else side=1;
        if(!a[u].ch[side]) break;
        u = a[u].ch[side];
      }
    }

    int v = NewNodeIdx();
    InitNode(a[v], k);
    if (root) {
      a[u].ch[side] = v, a[v].p = u;
    } else {
      root=v;
    }
    root = Splay(v);
    return 1;
  }

  // Merges two trees, all values of tree u must less than v.
  // Returns new root.
  int Merge(int u, int v) {
    assert(!a[u].p);
    assert(!a[v].p);
    if(u==0) return v;
    if(v==0) return u;
    u=FindMax(u);
    assert(!a[u].ch[1]);
    a[u].ch[1]=v; a[v].p=u;
    Maintain(u);
    return u;
  }

  // Returns false if k doesn't exist.
  bool Delete(int& root, K k) {
    int u = Find(root, k);
    if(!u) return 0;
    int v0 = a[u].ch[0], v1 = a[u].ch[1];
    a[v0].p = a[v1].p = 0;
    empty_idx.pb(u);
    root = Merge(v0, v1);
    return 1;
  }

 protected:
  inline virtual Node null_node() { return Node(); }
  inline virtual void InitValue(Node& u) {}
  inline virtual void Maintain(int u) {}

 private:
  VI empty_idx;

  int NewNodeIdx() {
    int u;
    if (!empty_idx.empty()) {
      u = empty_idx.back();
      empty_idx.pop_back();
    } else {
      u = SIZE(a);
      a.emplace_back();
    }
    return u;
  }

  void InitNode(Node& u, K k) {
    u.k = k;
    u.p = u.ch[0] = u.ch[1] = 0;
    InitValue(u);
  }

  void Rotate(int u) {
    int pu = a[u].p;
    if (!pu) return;
    int ppu = a[pu].p;
    int uside = Side(u);
    int uch = a[u].ch[uside ^ 1];
    if (ppu) a[ppu].ch[Side(pu)] = u;
    a[u].p = ppu;
    a[pu].ch[uside] = uch, a[uch].p = pu;
    a[u].ch[uside ^ 1] = pu, a[pu].p = u;
    Maintain(pu);
    Maintain(u);
  }
};

// Key is {l, r}. Value is {node count, subtree size}.
class SplayTree : public BaseSplayTree<PI, PI> {
 public:
  using K = PI;
  using V = PI;
  using Node = typename BaseSplayTree<K, V>::Node;

  void UpdateNode(int u) {
    a[u].v.first = a[u].k.second - a[u].k.first;
    Maintain(u);
  }

  void Debug() {
    if (!dbg) return;
    for (int u = 1; u < SIZE(a); ++u) {
      dpf("%d: %d %d, %d %d %d\n",
          u, a[u].k.first, a[u].k.second, a[u].p, a[u].ch[0], a[u].ch[1]);
    }
  }

 protected:
  inline virtual Node null_node() {
    Node u;
    u.v = {0, 0};
    return u;
  }

  inline virtual void InitValue(Node& u) {
    u.v.second = u.v.first = u.k.second - u.k.first;
  }

  inline virtual void Maintain(int u) {
    this->a[u].v.second = this->a[this->a[u].ch[0]].v.second +
                          this->a[this->a[u].ch[1]].v.second +
                          this->a[u].v.first;
  }
};

SplayTree st;
int root;

int QueryRange(int lu, int ru) {
  int res = st.a[lu].k.second - st.a[lu].k.first;
  if (lu == ru) return res;
  root = st.Splay(lu);

  int lu_rch = st.a[lu].ch[1];
  assert(lu_rch);
  st.a[lu_rch].p = 0;
  st.Splay(ru);
  st.a[lu].ch[1] = ru, st.a[ru].p = lu;
  res += st.a[ru].v.second - st.a[st.a[ru].ch[1]].v.second;

  return res;
}

int Query(int l,int r) {
  st.Debug();
  if (l >= r) return 0;
  int res = 0;
  int lu = 0, ru = 0;

  int u = st.Prev(root, {l, INF});
  dpf("start u: %d, %d %d\n", u, st.a[u].k.first, st.a[u].k.second);
  if(u) {
    if (st.a[u].k.second > l) {
      if(st.a[u].k.second >= r) {
        res += r - l;
        return res;
      }
      res += st.a[u].k.second - l;
    }
    lu = st.Next(root);
  } else {
    lu = st.FindMin(root);
  }

  u = st.Prev(root, {r, -INF});
  dpf("end u: %d, %d %d\n", u, st.a[u].k.first, st.a[u].k.second);
  if (u) {
    if (st.a[u].k.second >= r) {
      res += r - st.a[u].k.first;
      ru = st.Prev(root);
    } else {
      ru = u;
    }
  } else {
    ru = 0;
  }

  dpf("lu: %d, %d %d\n", lu, st.a[lu].k.first, st.a[lu].k.second);
  dpf("ru: %d, %d %d\n", ru, st.a[ru].k.first, st.a[ru].k.second);
  if (lu && ru && st.a[lu].k <= st.a[ru].k) res += QueryRange(lu, ru);
  return res;
}

void Add(int l, int r) {
  if (l >= r) return;
  int u = st.Prev(root, {l, INF});
  if (u && st.a[u].k.second >= l) {
    if (st.a[u].k.second >= r) return;
    st.a[u].k.second = r;
    st.UpdateNode(u);
  } else {
    st.Insert(root, {l, r});
    u = root;
  }

  while (1) {
    int v = st.Next(root, st.a[u].k);
    if (!v || st.a[v].k.first > st.a[u].k.second) break;
    root = st.Splay(u);
    UpdateMax(st.a[u].k.second, st.a[v].k.second);
    st.UpdateNode(u);
    st.Delete(root, st.a[v].k);
  }
}

void Solve() {
  int nq;
  scanf("%d",&nq);
  st.Reset(nq);
  root = 0;

  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 += 1 + C;
    if(t==1) {
      C = Query(l, r);
      printf("%d\n",C);
    } else {
      Add(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 SplayTree::Debug()':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
   32 |   #define dpf(...) 42
      |                    ^~
apple.cpp:274:7: note: in expansion of macro 'dpf'
  274 |       dpf("%d: %d %d, %d %d %d\n",
      |       ^~~
apple.cpp: In function 'int Query(int, int)':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
   32 |   #define dpf(...) 42
      |                    ^~
apple.cpp:322:3: note: in expansion of macro 'dpf'
  322 |   dpf("start u: %d, %d %d\n", u, st.a[u].k.first, st.a[u].k.second);
      |   ^~~
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
   32 |   #define dpf(...) 42
      |                    ^~
apple.cpp:337:3: note: in expansion of macro 'dpf'
  337 |   dpf("end u: %d, %d %d\n", u, st.a[u].k.first, st.a[u].k.second);
      |   ^~~
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
   32 |   #define dpf(...) 42
      |                    ^~
apple.cpp:349:3: note: in expansion of macro 'dpf'
  349 |   dpf("lu: %d, %d %d\n", lu, st.a[lu].k.first, st.a[lu].k.second);
      |   ^~~
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
   32 |   #define dpf(...) 42
      |                    ^~
apple.cpp:350:3: note: in expansion of macro 'dpf'
  350 |   dpf("ru: %d, %d %d\n", ru, st.a[ru].k.first, st.a[ru].k.second);
      |   ^~~
apple.cpp: In function 'void Solve()':
apple.cpp:32:20: warning: statement has no effect [-Wunused-value]
   32 |   #define dpf(...) 42
      |                    ^~
apple.cpp:387:5: note: in expansion of macro 'dpf'
  387 |     dpf("Query %d %d %d\n", t, l, r);
      |     ^~~
apple.cpp:379:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  379 |   scanf("%d",&nq);
      |   ~~~~~^~~~~~~~~~
apple.cpp:386:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  386 |     scanf("%d%d%d",&t,&l,&r);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100