| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 330030 | rk42745417 | 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.
/*
-------------- | /
| | /
| | /
| * |/ | | ------ *
| | | | / \
| | |\ | | | |\ |
\ | | | \ | | | | \ |
\ | | | \ | | \ / \ |
V | | \ \__/| ----- \ |
*/
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
/*-----------------------------------------------------------------------------------------------------*/
struct tree_node {
int l = -1, r = -1;
ll v;
tree_node(ll _v) { v = _v; }
};
vector<tree_node> nodes;
int segtree_t;
struct segtree {
int n, root = -1;
void init(int c) { n = c; }
void edt(int p, ll v) {
root = edt(0, n, root, p, v);
}
int edt(int l, int r, int id, int p, ll v) {
if(r <= p || p < l)
return id;
if(id == -1) {
nodes.push_back(tree_node(0));
id = segtree_t++;
}
if(l == r - 1) {
nodes[id].v = v;
return id;
}
int m = l + r >> 1;
nodes[id].l = edt(l, m, nodes[id].l, p, v);
nodes[id].r = edt(m, r, nodes[id].r, p, v);
nodes[id].v = 0;
if(~nodes[id].l)
nodes[id].v = nodes[nodes[id].l].v;
if(~nodes[id].r)
nodes[id].v = __gcd(nodes[id].v, nodes[nodes[id].r].v);
return id;
}
ll que(int l, int r) {
return que(0, n, root, l, r);
}
ll que(int l, int r, int id, int ql, int qr) {
if(qr <= l || r <= ql || id == -1)
return 0;
if(ql <= l && r <= qr)
return nodes[id].v;
int m = l + r >> 1;
return __gcd(que(l, m, nodes[id].l, ql, qr), que(m, r, nodes[id].r, ql, qr));
}
};
struct two_d_segtree {
int nr, nc, t = 0, root = -1;
struct node {
int l = -1, r = -1;
segtree v;
node(int c) { v.init(c); }
};
vector<node> arr;
void init(int x, int y) { nr = x, nc = y; }
void edt(int x, int y, ll v) {
root = edt(0, nr, x, y, root, v);
}
int edt(int l, int r, int x, int y, int id, ll v) {
if(l > x || r <= x)
return id;
if(id == -1) {
arr.push_back(node(nc));
id = t++;
}
//arr[id].v.edt(y, v);
if(l == r - 1)
return id;
int m = l + r >> 1;
arr[id].l = edt(l, m, x, y, arr[id].l, v);
arr[id].r = edt(m, r, x, y, arr[id].r, v);
return id;
}
ll que(int x1, int y1, int x2, int y2) {
return que(0, nr, root, x1, x2, y1, y2);
}
ll que(int l, int r, int id, int x1, int x2, int y1, int y2) {
if(r <= x1 || x2 <= l || id == -1)
return 0;
if(x1 <= l && r <= x2)
return arr[id].v.que(y1, y2);
int m = l + r >> 1;
return __gcd(que(l, m, arr[id].l, x1, x2, y1, y2), que(m, r, arr[id].r, x1, x2, y1, y2));
}
} tree;
void init(int r, int c) {
tree.init(r, c);
}
void update(int p, int q, ll k) {
tree.edt(p, q, k);
}
ll calculate(int p, int q, int u, int v) {
if(p > u)
swap(p, u);
if(q > v)
swap(q, v);
return tree.que(p, q, u + 1, v + 1);
}
/*
signed main() { EmiliaMyWife
int r, c, n;
cin >> r >> c >> n;
tree.init(r, c);
while(n--) {
int t;
cin >> t;
if(t == 1) {
int x, y;
ll k;
cin >> x >> y >> k;
tree.edt(x, y, k);
}
else {
int a, b, c, d;
cin >> a >> b >> c >> d;
if(a > c)
swap(a, c);
if(b > d)
swap(b, d);
//cout << tree.que(a, b, c + 1, d + 1) << '\n';
cout << "0\n";
}
}
}
*/