| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 490548 | cs142857 | Game (IOI13_game) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
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 = gcd(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;
void Solve() {
int R,C;
scanf("%d%d", &R, &C);
st.Init(R - 1, C - 1);
int root = st.NewNode();
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);
st.Set(x, y, w, root);
} else {
int lx, rx, ly, ry;
scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
printf("%lld\n", st.Query(lx, rx, ly, ry, root));
}
}
}
int main() {
int t = 1;
// scanf("%d", &t);
for (int i = 1; i <= t; ++i) {
// printf("Case #%d: ", i);
Solve();
}
return 0;
}