답안 #479880

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

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

Compilation message

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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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 4 ms 460 KB Output is correct
5 Correct 5 ms 492 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 21 ms 700 KB Output is correct
9 Correct 42 ms 912 KB Output is correct
10 Correct 43 ms 824 KB Output is correct
11 Correct 47 ms 836 KB Output is correct
12 Correct 41 ms 928 KB Output is correct
13 Correct 45 ms 960 KB Output is correct
14 Correct 46 ms 1024 KB Output is correct
15 Correct 46 ms 1096 KB Output is correct
16 Correct 47 ms 1152 KB Output is correct
17 Correct 43 ms 964 KB Output is correct
18 Correct 44 ms 932 KB Output is correct
19 Correct 46 ms 1024 KB Output is correct
20 Correct 45 ms 960 KB Output is correct