| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 595731 | Bobaa | 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 "game.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
struct TreapNode {
TreapNode *l, *r;
int pos, key, mn, mx;
long long val, g;
TreapNode(int position, long long value) {
l = r = nullptr;
mn = mx = pos = position;
key = rng();
val = g = value;
}
void update() {
g = val;
if (l) g = __gcd(g, l -> g);
if (r) g = __gcd(g, r -> g);
mn = (l ? l -> mn : pos);
mx = (r ? r -> mx : pos);
}
};
struct Treap {
Treapnode *root;
Treap() {
root = nullptr;
}
void split(Treapnode *t, int pos, Treapnode *&l, Treapnode *&r) {
if (t == nullptr) {
l = r = nullptr;
return;
}
if (t -> pos < pos) {
split(t -> r, pos, l, r);
t -> r = l;
l = t;
} else {
split(t -> l, pos, l, r);
t -> l = r;
r = t;
}
t -> update();
}
Treapnode* merge(Treapnode *l, Treapnode *r) {
if (!l) return r;
if (!r) return l;
if (l -> key < r -> key) {
l -> r = merge(l -> r, r);
l -> update();
return l;
} else {
r -> l = merge(l, r -> l);
r -> update();
return r;
}
}
bool find(int pos) {
Treapnode *t = root;
while (t) {
if (t -> pos == pos) return true;
if (t -> pos > pos) t = t -> l;
else t = t -> r;
}
return false;
}
void update(TreapNode *t, int pos, long long value) {
if (t -> pos == pos) {
t -> val = value;
t -> update();
return;
}
if (t -> pos > pos) update(t -> l, pos, value);
else update(t -> r, pos, value);
t -> update();
}
void insert(int pos, long long value) {
if (find(pos)) {
update(root, pos, value);
return;
}
Treapnode *l, *r;
split(root, pos, l, r);
root = merge(merge(l, new TreapNode(pos, value)), r);
}
long long query(TreapNode *t, int l, int r) {
if (t -> mx < l || t -> mn > r) return 0LL;
if (l <= t -> mn && t -> mx <= r) return t -> g;
long long res = 0;
if (l <= t -> pos && t -> pos <= r) res = t -> val;
if (t -> l) res = __gcd(res, query(t -> l, l, r));
if (t -> r) res = __gcd(res, query(t -> r, l, r));
return res;
}
long long query(int l, int r) {
if (!root) return 0LL;
return query(root, l, r);
}
};
struct SegTree {
SegTree *l, *r;
Treap treap;
int lo, hi;
SegTree() {
l = r = nullptr;
}
SegTree(int st, int en) {
l = r = nullptr;
lo = st;
hi = en;
}
void new_left() {
if (!l) l = new SegTree(lo, (lo + hi) / 2);
}
void new_right() {
if (!r) r = new SegTree((lo + hi) / 2 + 1, hi);
}
void fix(int pos) {
long long val = 0;
if (l) val = __gcd(val, l -> treap.query(pos, pos));
if (r) val = __gcd(val, r -> treap.query(pos, pos));
treap.insert(pos, val);
}
void update(int x, int y, long long val) {
if (hi < x || lo > x) return;
if (lo == hi) {
treap.insert(y, val);
return;
}
int mid = (lo + hi) / 2;
if (x <= mid) {
new_left();
l -> update(x, y, val);
} else {
new_right();
r -> update(x, y, val);
}
fix(y);
}
long long query(int t, int b, int st, int en) {
if (hi < t || lo > b) return 0LL;
if (t <= lo && hi <= b) return treap.query(st, en);
long long ans = 0;
if (l) ans = __gcd(ans, l -> query(t, b, st, en));
if (r) ans = __gcd(ans, r -> query(t, b, st, en));
return ans;
}
};
SegTree segtree;
void init(int R, int C) {
segtree = SegTree(0, R - 1);
}
void update(int P, int Q, long long K) {
segtree.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return segtree.query(P, U, Q, V);
}