Submission #490704

#	Time	Username	Problem	Language	Result	Execution time	Memory
490704		cs142857	Game (IOI13_game)	C++17	Compilation error	0 ms	0 KiB

game

// IOI 2013, Game
// Sparse Segment Tree + Splay Tree
// Test: https://oj.uz/submission/490590

#include "game.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

#ifdef DBG
  #define dbg 1
  #define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
  #define Dps(...) Dbgs(__VA_ARGS__)
#else
  #define dbg 0
  #define dpf(...) 42
  #define Dps(...) 42
#endif
 
#define SIZE(c) int((c).size())
#define FOR(i,l,r) for(int i = (l); i < (r); ++i)
#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 bool UpdateMax(T& x, T v) {
  if(v > x) {x=v; return 1;} else return 0;
}
template <typename T> inline bool UpdateMin(T& x, T v) {
  if(v < x) {x=v; return 1;} else return 0;
}

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

inline namespace output {  // Only for debug now.
template <class T>
void PrSep(std::ostream& os, string, const T& t) { os << t; }
template <class T, class... U>
void PrSep(std::ostream& os, string sep, const T& t, const U&... u) {
  PrSep(os, sep, t); os << sep; PrSep(os, sep, u...);
}

// Print w/ spaces, end with newline
void Ps() { cout << "\n"; }
template<class ...T> void Ps(const T&... t) { PrSep(cout," ",t...); Ps(); } 
template<class ...T> void Dbgs(const T&... t) { PrSep(cerr," ",t...); cerr << endl; } 
}  // namespace output

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

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

  void Init(V identity, int init_capacity = 0) {
    this->identity = identity;
    a.resize(1);
    a[0] = 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 is maximal and < k, or 0 not found.
  int Prev(int& root, K k) {
    bool inserted = Insert(root, k, identity).second;
    int u = a[root].ch[0];
    while (a[u].ch[1]) u = a[u].ch[1];
    if (inserted) 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 inserted = Insert(root, k, identity).second;
    int u = a[root].ch[1];
    while (a[u].ch[0]) u = a[u].ch[0];
    if (inserted) assert(Delete(root, k));
    if (u) root = Splay(u);
    return u;
  }

  // If the key already exists, do not insert new value if overwrite is false,
  // and returns pair { the existing value of the key,
  //   whether the new value is inserted }.
  // Otherwise, if the key doesn't exist, returns {v, true}.
  pair<V, bool> Insert(int& root, K k, V v, bool overwrite = false) {
    int u = root;
    int side = 0;
    if (root) {
      while (1) {
        if (k == a[u].k) {
          root = Splay(u);
          if (overwrite) {
            V prev = a[u].v;
            a[u].v = v;
            Maintain(u);
            return {prev, 1};
          } else {
            return {a[u].v, 0};
          }
        }
        if (k < a[u].k) side=0; else side=1;
        if(!a[u].ch[side]) break;
        u = a[u].ch[side];
      }
    }

    int new_u = NewNodeIdx();
    a[new_u] = Node(k, v);
    if (root) {
      a[u].ch[side] = new_u, a[new_u].p = u;
    } else {
      root = new_u;
    }
    root = Splay(new_u);
    return {v, 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;
  }

  V RangeQuery(int& root, K min_k, K max_k) {
    if (!root) return identity;
    if (!Next(root, max_k)) {
      if (!Prev(root, min_k)) return a[root].v;
      int root_r = a[root].ch[1];
      return root_r ? a[root_r].v : identity;
    }

    int root_l = a[root].ch[0];
    if (!root_l) return identity;
    a[root_l].p = 0;
    int u = Prev(root_l, min_k);
    a[root_l].p = root;
    a[root].ch[0] = root_l;
    if (!u) return a[root_l].v;
    int root_lr = a[root_l].ch[1];
    return root_lr ? a[root_lr].v : identity;
  }

  friend std::ostream& operator<<(std::ostream& os, const SplayTree<K, V>& t) {
    for (int i = 1; i < SIZE(t.a); ++i) {
      os << i << ": {" << t.a[i].k << " " << t.a[i].v << "} {"
         << t.a[i].p << " " << t.a[i].ch[0] << " " << t.a[i].ch[1] << "}\n";
    }
    return os;
  }

 protected:
  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 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);
  }
};

const int MAX_SEG_NODE = 2000000;
const int MAX_SPLAY_NODE = 5000000;

// Splay Tree class, with weight and weight GCD-merge of sub-tree.
template <typename K, typename W>
class SplayTreeWithWeight : public SplayTree<K, pair<W, W>> {
 public:
  using T = pair<W, W>;
  using Node = typename SplayTree<K, T>::Node;

  void Init() {
    SplayTree<K, T>::Init({0, 0}, MAX_SPLAY_NODE);
  }

  void Set(int& root, K k, W w) {
    SplayTree<K, T>::Insert(root, k, {w, w}, true);
    Maintain(root);
  }

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

template <typename T>
class BaseDySegTree {
 public:
  struct Node {
    int l = -1, r = -1;
    T v;
  };
  int max_idx;
  vector<Node> a;

  inline virtual T default_value() const = 0;

  void Init(int max_idx) {
    assert(max_idx >= -1);
    this->max_idx = max_idx;
    a.clear();
    a.reserve(MAX_SEG_NODE);
  }

  int NewNode() {
    int res = SIZE(a);
    a.emplace_back();
    a.back().v = default_value();
    return res;
  }
};

template <typename T>
class DySegTree2D : public BaseDySegTree<int> {
 public:
  int max_y;
  SplayTreeWithWeight<int, i64> splay;

  inline virtual int default_value() const { return 0; }

  void Init(int max_x, int max_y) {
    BaseDySegTree<int>::Init(max_x);
    this->max_y = max_y;
    splay.Init();
  }

  int Update(int x, int y, T v, int p) { return Update(x, y, v, p, 0, this->max_idx); }

  T Query(int qlx, int qrx, int qly, int qry, int p) {
    return Query(qlx, qrx, qly, qry, p, 0, this->max_idx);
  }

 private:
  inline void NewLeft(int p) {
    if (a[p].l < 0) a[p].l = NewNode();
  }
  inline void NewRight(int p) {
    if (a[p].r < 0) a[p].r = NewNode();
  }

  T Update(int x, int y, T v, int p, int li, int ri) {
    T res;
    if (li == ri) {
      res = v;
    } else {
      int m = (li + ri) >> 1;
      if (x <= m) {
        NewLeft(p);
        res = Update(x, y, v, a[p].l, li, m);
        if (a[p].r >= 0) res = gcd2(res, QueryY(a[a[p].r].v, y, y));
      } else {
        NewRight(p);
        res = Update(x, y, v, a[p].r, m + 1, ri);
        if (a[p].l >= 0) res = gcd2(res, QueryY(a[a[p].l].v, y, y));
      }
    }
    splay.Set(a[p].v, y, res);
    return res;
  }

  T Query(int qlx, int qrx, int qly, int qry, int p, int lx, int rx) {
    if (p < 0 || qlx > rx || qrx < lx) return 0;
    T res;
    if (qlx <= lx && qrx >= rx) {
      res = QueryY(a[p].v, qly, qry);
    } else {
      int m = (lx + rx) >> 1;
      res = gcd2(Query(qlx, qrx, qly, qry, this->a[p].l, lx, m),
                 Query(qlx, qrx, qly, qry, this->a[p].r, m + 1, rx));
    }
    return res;
  }

  T QueryY(int& root, int qly, int qry) {
    return splay.RangeQuery(root, qly, qry).second;
  }
};

DySegTree2D<i64> st;
int root;

void init(int R, int C) {
  st.Init(R - 1, C - 1);
  root = st.NewNode();
}

void update(int x, int y, i64 w) {
  st.Update(x, y, w, root);
}

i64 calculate(int lx, int ly, int rx, int ry) {
  return st.Query(lx, rx, ly, ry, root);
}

/*
void Solve() {
  int R,C;
  scanf("%d%d",&R,&C);
  init(R, C);
  int n;
  scanf("%d",&n);
  while(n--) {
    int t;
    scanf("%d",&t);
    if (t == 1) {
      int x, y;
      i64 w;
      scanf("%d%d%lld", &x, &y, &w);
      update(x, y, w);
    } else {
      int lx,rx,ly,ry;
      scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
      printf("%lld\n", calculate(lx, ly, rx, ry));
    }
  }
}

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

  return 0;
}
*/

Compilation message (stderr)

game.cpp: In member function 'int SplayTree<K, V>::Merge(int, int)':
game.cpp:200:7: error: there are no arguments to 'FindMax' that depend on a template parameter, so a declaration of 'FindMax' must be available [-fpermissive]
  200 |     u=FindMax(u);
      |       ^~~~~~~
game.cpp:200:7: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
game.cpp: In instantiation of 'bool SplayTree<K, V>::Delete(int&, K) [with K = int; V = std::pair<long long int, long long int>]':
game.cpp:151:19:   required from 'int SplayTree<K, V>::Next(int&, K) [with K = int; V = std::pair<long long int, long long int>]'
game.cpp:220:10:   required from 'V SplayTree<K, V>::RangeQuery(int&, K, K) [with K = int; V = std::pair<long long int, long long int>]'
game.cpp:394:28:   required from 'T DySegTree2D<T>::QueryY(int&, int, int) [with T = long long int]'
game.cpp:369:42:   required from 'T DySegTree2D<T>::Update(int, int, T, int, int, int) [with T = long long int]'
game.cpp:346:55:   required from 'int DySegTree2D<T>::Update(int, int, T, int) [with T = long long int]'
game.cpp:407:26:   required from here
game.cpp:209:17: error: 'Find' was not declared in this scope
  209 |     int u = Find(root, k);
      |             ~~~~^~~~~~~~~