제출 #490551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490551		cs142857	Game (IOI13_game)	C++17	0 / 100	1 ms	332 KiB

game

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

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;
  inline virtual void CombineNode(const T& lv, const T& rv, T& v) = 0;

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

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

  T Query(int qli, int qri, int p) {
    return Query(qli, qri, p, 0, this->max_idx);
  }

 protected:
  // Combines left and right children to current node.
  inline void PushUp(int p) {
    CombineNode(
        (a[p].l < 0) ? default_value() : a[a[p].l].v,
        (a[p].r < 0) ? default_value() : a[a[p].r].v,
        a[p].v);
  }

 private:
  T Query(int qli, int qri, int p, int li, int ri) {
    T res;
    if (p < 0 || qli > ri || qri < li) res = default_value();
    else if (qli <= li && qri >= ri) {
      res = this->a[p].v;
    } else {
      int m = (li + ri) >> 1;
      CombineNode(Query(qli, qri, this->a[p].l, li, m),
                  Query(qli, qri, this->a[p].r, m + 1, ri), res);
    }
    return res;
  }
};

template <typename T>
class DySegTree : public BaseDySegTree<T> {
 public:
  inline virtual T default_value() const { return 0; }
  inline virtual void CombineNode(const T& lv, const T& rv, T& v) {
    v = gcd2(lv, rv);
  }

  int Set(int i, T v, int p) { return Set(i, v, p, 0, this->max_idx); }

 private:
  int Set(int i, T v, int p, int li, int ri) {
    if (p < 0) p = this->NewNode();
    if (li == ri) {
      this->a[p].v = v;
    } else {
      int m = (li + ri) >> 1;
      if (i <= m) this->a[p].l = Set(i, v, this->a[p].l, li, m);
      else this->a[p].r = Set(i, v, this->a[p].r, m + 1, ri);
      this->PushUp(p);
    }
    return p;
  }
};

template <typename T>
class DySegTree2D : public BaseDySegTree<int> {
 public:
  DySegTree<T> y_st;

  inline virtual int default_value() const { return -1; }

  void Init(int max_x, int max_y) {
    BaseDySegTree<int>::Init(max_x);
    y_st.Init(max_y);
  }

  int Set(int x, int y, T v, int p) { return Set(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);
  }

 protected:
  inline virtual void CombineNode(const int& lv, const int& rv, int& v) {}
  inline void PushUp(int p) {}

 private:
  int Set(int x, int y, T v, int p, int li, int ri) {
    if (p < 0) p = NewNode();
    a[p].v = y_st.Set(y, v, a[p].v);
    if (li < ri) {
      int m = (li + ri) >> 1;
      if (x <= m) a[p].l = Set(x, y, v, a[p].l, li, m);
      else a[p].r = Set(x, y, v, a[p].r, m + 1, ri);
    }
    return p;
  }

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

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.Set(x, y, w, root);
}

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20