# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
774181 | alontanay | 게임 (IOI13_game) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
ll safe_gcd(ll a, ll b) {
if (a == 0 || b == 0) {
return a + b;
}
return gcd(a, b);
}
template <typename T>
struct node {
T val, gc;
int prior;
pi pos;
node *l = nullptr, *r = nullptr;
node(T v, pi pos) : val(v), gc(v), pos(pos), prior(rand()) {}
};
template <typename T>
using node_ptr = struct node<T> *;
template <typename T>
void print(node_ptr<T> t, int id = 0) {
for (int i = 0; i < id; i++) {
cout << " ";
}
if (!t) {
cout << "-" << endl;
return;
}
cout << t->val << endl;
print(t->l, id + 1);
print(t->r, id + 1);
}
template <typename T>
T gc(node_ptr<T> t) {
return t ? t->gc : 0;
}
template <typename T>
void pull(node_ptr<T> t) {
if (t) {
t->gc = safe_gcd(t->val, safe_gcd(gc(t->l), gc(t->r)));
}
}
template <typename T>
void merge(node_ptr<T> &t, node_ptr<T> l, node_ptr<T> r) {
if (!l || !r) {
t = l ? l : r;
return;
}
if (l->prior > r->prior) {
merge(l->r, l->r, r);
t = l;
} else {
merge(r->l, l, r->l);
t = r;
}
pull(t);
}
template <typename T>
void split(node_ptr<T> t, node_ptr<T> &l, node_ptr<T> &r, pi key) {
if (!t) {
return void(l = r = 0);
}
if (t->pos >= key) {
split(t->l, l, t->l, key);
r = t;
} else {
split(t->r, t->r, r, key);
l = t;
}
pull(t);
}
template <typename T>
void insert(node_ptr<T> &t, node_ptr<T> val) {
node_ptr<T> l = nullptr, m = nullptr, r = nullptr;
// cout << "A" << endl;
split(t, l, r, val->pos);
// cout << "B" << endl;
split(r, m, r, {val->pos.f, val->pos.s + 1});
m = val;
// cout << "D" << endl;
merge(r, m, r);
// cout << "X" << endl;
// cout << gc(l) << " " << gc(r) << " " << gc(t) << endl;
merge(t, l, r);
// cout << "A" << endl;
}
template <typename T>
ll query(node_ptr<T> &t, pi a, pi b) {
node_ptr<T> l = nullptr, m = nullptr, r = nullptr;
split(t, m, r, b);
split(m, l, m, a);
// print(m);
ll res = gc(m);
merge(m, l, m);
merge(t, m, r);
return res;
}
struct SegTreap {
node_ptr<ll> val = nullptr;
int l, r, mid;
SegTreap *ls, *rs;
SegTreap(int l, int r) : l(l), r(r), mid((l + r) / 2) {}
ll query_rect(int a, int b, int c, int d) {
// cout << "~ QUERY" << endl;
if (a >= r || b <= l) {
return 0;
}
if (a <= l && b >= r) {
return query<ll>(val, {c, a}, {d - 1, b});
}
return safe_gcd(ls ? ls->query_rect(a, b, c, d) : 0,
rs ? rs->query_rect(a, b, c, d) : 0);
}
void update(int a, pi pos, ll k) {
node_ptr<ll> new_node = new node<ll>(k, pos);
// cout << "~ INSERT " << l << " - " << r << endl;
insert<ll>(val, new_node);
// cout << "DONE" << endl;
// print(val);
if (l + 1 == r) {
return;
}
if (a < mid) {
if (!ls) {
ls = new SegTreap(l, mid);
}
ls->update(a, pos, k);
} else {
if (!rs) {
rs = new SegTreap(mid, r);
}
rs->update(a, pos, k);
}
}
};
const int INF = 1e9 + 1;
SegTreap seg2d(0, INF);
void init(int R, int C) { srand(time(0)); }
void update(int P, int Q, long long K) {
// cout << "ADD " << P << " " << Q << " " << K << endl;
seg2d.update(P, {Q, P}, K);
}
long long calculate(int P, int Q, int U, int V) {
// cout << "CALC " << P << " " << Q << " " << U << " " << V << endl;
return seg2d.query_rect(P, U + 1, Q, V + 1);
}