Submission #490925

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
490925	2021-11-29T20:01:39 Z	cs142857	Game (IOI13_game)	C++17	100 / 100	3290 ms	49776 KB

game

// IOI 2013, Game
// Sparse Segment Tree + Treap
// Test: https://www.luogu.com.cn/record/63941489

#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 {
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) {
  return os << "{" << v.first << " " << v.second << "}";
}
}  // namespace output

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

const int MAX_SEG_NODE = 2000000;
const int MAX_INNER_TREE_NODE = 4000000;

// Treap, Split/Merge, without rotation.
// Source: https://cp-algorithms.com/data_structures/treap.html
// Works like map<K, V>, do not allow duplicate key.
template <typename K, typename V>
class Treap {
 public:
  struct TrNode {
    K k;
    V v;
    int pr = rand();
    K min_k, max_k;
    int l = 0, r = 0;
    TrNode() {}
    TrNode(K k, V v) : k(k), v(v) {
      min_k = max_k = k;
    }
  };
  vector<TrNode> a;
  V identity;

  inline virtual void Maintain(int u) {
    if (a[u].l) a[u].min_k = min(a[u].k, a[a[u].l].min_k);
    if (a[u].r) a[u].max_k = max(a[u].k, a[a[u].r].max_k);
  }

  void Init(V identity, int init_capacity = 0) {
    this->identity = identity;
    a.resize(1);
    a[0] = TrNode();
    a[0].v = identity;
    a.reserve(init_capacity + 1);
    empty_idx.clear();
  }

  void Split(int root, K k, int &l, int &r) {
    if (!root) {
      l = r = 0;
    } else if (a[root].k <= k) {
      Split(a[root].r, k, a[root].r, r);
      l = root;
    } else {
      Split(a[root].l, k, l, a[root].l);
      r = root;
    }
    if (l) Maintain(l);
    if (r) Maintain(r);
  }

  // Merges two trees, all values of tree u must less than v.
  // Returns new root.
  int Merge(int l, int r) {
    if (l == 0) return r;
    if (r == 0) return l;
    int u;
    if (a[l].pr > a[r].pr) {
      a[l].r = Merge(a[l].r, r);
      u = l;
    } else {
      a[r].l = Merge(l, a[r].l);
      u = r;
    }
    Maintain(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 u;
      if (a[u].k > k)
        u = a[u].l;
      else 
        u = a[u].r;
    }
    return 0;
  }

  // If the key already exists, returns {the existing node, false}.
  // Otherwise, returns {the newly inserted node, true}, the value of the
  // newly inserted node will be `identity`.
  pair<int, bool> Insert(int& root, K k) {
    int u = Find(root, k);
    if (u) return {u, false};
    u = NewNodeIdx();
    a[u] = TrNode(k, identity);
    int l, r;
    Split(root, k, l, r);
    root = Merge(Merge(l, u), r);
    return {u, true};
  }

  void MaintainFromRoot(int root, int u) {
    if (a[u].k < a[root].k)
      MaintainFromRoot(a[root].l, u);
    else if (a[u].k > a[root].k)
      MaintainFromRoot(a[root].r, u);
    Maintain(root);
  }

  friend std::ostream& operator<<(std::ostream& os, const Treap<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].pr
         << " {" << t.a[i].l << " " << t.a[i].r << "}\n";
    }
    return os;
  }

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

// Treap, with weight and weight GCD-merge of sub-tree.
class TreapWithWeight : public Treap<int, pair<i64, i64>> {
 public:
  using K = int;
  using T = pair<i64, i64>;
  using Base = Treap<K, T>;
  using TrNode = typename Base::TrNode;

  void Init() {
    Base::Init({0, 0}, MAX_INNER_TREE_NODE);
  }

  inline virtual void Maintain(int u) {
    Base::Maintain(u);
    a[u].v.second = gcd2(gcd2(a[a[u].l].v.second, a[a[u].r].v.second),
                         a[u].v.first);
  }

  void Set(int& root, K k, i64 w) {
    int u = Base::Insert(root, k).first;
    a[u].v.first = w;
    Base::MaintainFromRoot(root, u);
  }

  i64 RangeQuery(int root, K min_k, K max_k) {
    i64 res = 0;
    if (!root || a[root].max_k < min_k || a[root].min_k > max_k)
      ;
    else if (a[root].min_k >= min_k && a[root].max_k <= max_k)
      res = a[root].v.second;
    else {
      if (a[root].k >= min_k && a[root].k <= max_k) res = a[root].v.first;
      res = gcd2(res, RangeQuery(a[root].l, min_k, max_k));
      res = gcd2(res, RangeQuery(a[root].r, min_k, max_k));
    }
    return res;
  }
};

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;
  TreapWithWeight tree;

  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;
    tree.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));
      }
    }
    tree.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 tree.RangeQuery(root, qly, qry);
  }
};

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

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	296 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	649 ms	10752 KB	Output is correct
5	Correct	269 ms	10552 KB	Output is correct
6	Correct	666 ms	8032 KB	Output is correct
7	Correct	727 ms	7712 KB	Output is correct
8	Correct	433 ms	7148 KB	Output is correct
9	Correct	723 ms	7792 KB	Output is correct
10	Correct	682 ms	7504 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	292 KB	Output is correct
3	Correct	2 ms	316 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	849 ms	12100 KB	Output is correct
13	Correct	1539 ms	7048 KB	Output is correct
14	Correct	218 ms	5464 KB	Output is correct
15	Correct	1561 ms	8188 KB	Output is correct
16	Correct	255 ms	9688 KB	Output is correct
17	Correct	881 ms	9020 KB	Output is correct
18	Correct	1473 ms	11188 KB	Output is correct
19	Correct	1265 ms	11332 KB	Output is correct
20	Correct	1258 ms	10796 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	292 KB	Output is correct
12	Correct	636 ms	10784 KB	Output is correct
13	Correct	262 ms	10556 KB	Output is correct
14	Correct	662 ms	7988 KB	Output is correct
15	Correct	733 ms	7744 KB	Output is correct
16	Correct	435 ms	7120 KB	Output is correct
17	Correct	725 ms	7848 KB	Output is correct
18	Correct	691 ms	7620 KB	Output is correct
19	Correct	847 ms	12024 KB	Output is correct
20	Correct	1557 ms	6936 KB	Output is correct
21	Correct	227 ms	5496 KB	Output is correct
22	Correct	1551 ms	8044 KB	Output is correct
23	Correct	257 ms	9696 KB	Output is correct
24	Correct	871 ms	8856 KB	Output is correct
25	Correct	1494 ms	11284 KB	Output is correct
26	Correct	1314 ms	11284 KB	Output is correct
27	Correct	1266 ms	10676 KB	Output is correct
28	Correct	383 ms	27972 KB	Output is correct
29	Correct	1469 ms	30628 KB	Output is correct
30	Correct	1908 ms	22084 KB	Output is correct
31	Correct	1690 ms	18672 KB	Output is correct
32	Correct	325 ms	10116 KB	Output is correct
33	Correct	477 ms	10312 KB	Output is correct
34	Correct	355 ms	24328 KB	Output is correct
35	Correct	1030 ms	19648 KB	Output is correct
36	Correct	2238 ms	28452 KB	Output is correct
37	Correct	1778 ms	28660 KB	Output is correct
38	Correct	1802 ms	27988 KB	Output is correct
39	Correct	1405 ms	24344 KB	Output is correct
40	Correct	1 ms	204 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	288 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	264 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	646 ms	10712 KB	Output is correct
13	Correct	260 ms	10572 KB	Output is correct
14	Correct	661 ms	7992 KB	Output is correct
15	Correct	727 ms	7764 KB	Output is correct
16	Correct	437 ms	7132 KB	Output is correct
17	Correct	710 ms	8080 KB	Output is correct
18	Correct	686 ms	7536 KB	Output is correct
19	Correct	842 ms	12068 KB	Output is correct
20	Correct	1529 ms	6844 KB	Output is correct
21	Correct	219 ms	5580 KB	Output is correct
22	Correct	1538 ms	8056 KB	Output is correct
23	Correct	259 ms	9820 KB	Output is correct
24	Correct	865 ms	9056 KB	Output is correct
25	Correct	1461 ms	11348 KB	Output is correct
26	Correct	1265 ms	11284 KB	Output is correct
27	Correct	1253 ms	10760 KB	Output is correct
28	Correct	392 ms	27972 KB	Output is correct
29	Correct	1466 ms	30716 KB	Output is correct
30	Correct	1904 ms	22012 KB	Output is correct
31	Correct	1667 ms	18560 KB	Output is correct
32	Correct	323 ms	10116 KB	Output is correct
33	Correct	476 ms	10308 KB	Output is correct
34	Correct	357 ms	24356 KB	Output is correct
35	Correct	1031 ms	19636 KB	Output is correct
36	Correct	2217 ms	28508 KB	Output is correct
37	Correct	1710 ms	28636 KB	Output is correct
38	Correct	1760 ms	28292 KB	Output is correct
39	Correct	596 ms	47656 KB	Output is correct
40	Correct	2643 ms	49776 KB	Output is correct
41	Correct	3027 ms	38680 KB	Output is correct
42	Correct	2669 ms	31048 KB	Output is correct
43	Correct	801 ms	44584 KB	Output is correct
44	Correct	423 ms	10432 KB	Output is correct
45	Correct	1446 ms	24492 KB	Output is correct
46	Correct	3290 ms	48504 KB	Output is correct
47	Correct	3273 ms	48640 KB	Output is correct
48	Correct	3208 ms	48216 KB	Output is correct
49	Correct	0 ms	204 KB	Output is correct