| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 382852 | 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;
/*--------------------------------------------------------------------------------------*/
#include "game.h"
const int N = 1e6 + 25;
mt19937 rnd(time(0));
struct segtree {
struct Treap {
struct node {
int l, r, key, pri;
ll v, gd;
node(): l(0), r(0), key(0), pri(0), v(0), gd(0) { }
node(int p): l(0), r(0), key(p), pri(rnd()), v(0), gd(0) { }
} arr[N * 15];
int t = 1;
inline int new_node(int x) {
arr[t] = node(x);
return t++;
}
inline ll gd(int p) { return p ? arr[p].gd : 0; }
inline void pull(int p) { arr[p].gd = __gcd(__gcd(gd(arr[p].l), arr[p].v), gd(arr[p].r)); }
int merge(int a, int b) {
if(!a || !b)
return a ? a : b;
assert(arr[a].key < arr[b].key);
if(arr[a].pri > arr[b].pri) {
arr[a].r = merge(arr[a].r, b);
pull(a);
return a;
}
else {
arr[b].l = merge(a, arr[b].l);
pull(b);
return b;
}
}
void split(int rt, int &a, int &b, int k) {
if(!rt)
return a = b = 0, void();
if(arr[rt].key < k) {
a = rt;
split(arr[rt].r, arr[a].r, b, k);
pull(a);
}
else {
b = rt;
split(arr[rt].l, a, arr[b].l, k);
pull(b);
}
}
void travesal(int p) {
if(!p)
return;
travesal(arr[p].l);
cout << arr[p].v << ' ';
travesal(arr[p].r);
}
int edt(int rt, int p, ll v) {
int a, b, c;
split(rt, b, c, p + 1);
split(b, a, b, p);
if(!b)
b = new_node(p);
arr[b].v = arr[b].gd = v;
rt = merge(a, b);
rt = merge(rt, c);
return rt;
}
ll que(int rt, int l, int r) { // [l, r)
int a, b, c;
split(rt, b, c, r);
split(b, a, b, l);
pull(b);
ll x = arr[b].gd;
rt = merge(a, b);
rt = merge(rt, c);
return x;
}
} treap;
struct node {
int l, r, v;
node(): l(0), r(0), v(0) { }
} arr[N];
int r, c, t = 1, rt;
void init(int _r, int _c) {
r = _r;
c = _c;
}
int edt(int id, int l, int r, int p, int q, ll v) {
if(p < l || r <= p)
return id;
if(!id)
id = t++;
arr[id].v = treap.edt(arr[id].v, q, v);
if(l == r - 1)
return id;
int m = l + r >> 1;
arr[id].l = edt(arr[id].l, l, m, p, q, v);
arr[id].r = edt(arr[id].r, m, r, p, q, v);
return id;
}
ll que(int id, int l, int r, int ql, int qr, int up, int dw) {
if(r <= ql || qr <= l || !id)
return 0;
if(ql <= l && r <= qr) {
return treap.que(arr[id].v, up, dw);
}
int m = l + r >> 1;
return __gcd(que(arr[id].l, l, m, ql, qr, up, dw), que(arr[id].r, m, r, ql, qr, up, dw));
}
inline void edt(int p, int q, ll v) { rt = edt(rt, 0, r, p, q, v); }
inline ll que(int p, int q, int u, int v) { return que(rt, 0, r, p, u, q, v); }
} tree;
void init(int r, int c) {
tree.init(r, c);
}
void update(int p, int q, ll k) {
tree.edt(p, q, k);
}
long long calculate(int p, int q, int u, int v) {
return tree.que(p, q, u + 1, v + 1);
}
/*
signed main() { EmiliaMyWife
int r, c, q;
cin >> r >> c >> q;
init(r, c);
while(q--) {
int t;
cin >> t;
if(t == 1) {
int p, q; ll k;
cin >> p >> q >> k;
update(p, q, k);
}
else {
int p, q, u, v;
cin >> p >> q >> u >> v;
cout << calculate(p, q, u, v) << '\n';
}
}
}
*/