| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 681017 | nutella | 게임 (IOI13_game) | C++11 | 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 <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
#define gcd(a, b) __gcd(a, b)
struct segtree {
int l, r;
ll d = 0;
segtree *left = nullptr, *right = nullptr;
void pull() {
d = gcd(left ? left->d : 0, right ? right->d : 0);
}
void update(int i, ll k) {
if (l + 1 == r) {
d = k;
} else {
int mid = (l + r) / 2;
if (i < mid) {
if (!left) {
left = new segtree({l, mid});
}
left->update(i, k);
} else {
if (!right) {
right = new segtree({mid, r});
}
right->update(i, k);
}
pull();
}
}
ll query(int lx, int rx) {
if (lx >= r || rx <= l) {
return 0;
} else if (lx <= l && r <= rx) {
return d;
} else {
ll ans = 0;
if (left) {
ans = gcd(ans, left->query(lx, rx));
}
if (right) {
ans = gcd(ans, right->query(lx, rx));
}
return ans;
}
}
};
int R, C;
struct SegmentTree {
int l, r;
segtree *st = nullptr;
SegmentTree *left = nullptr, *right = nullptr;
void build_st() {
if (!st) {
st = new segtree({0, C});
}
}
ll simple_query(int y) {
if (!st) {
return 0;
} else {
return st->query(y, y + 1);
}
}
void update(int x, int y, ll k) {
build_st();
if (l + 1 == r) {
st->update(y, k);
} else {
int mid = (l + r) / 2;
if (x < mid) {
if (!left) {
left = new SegmentTree({l, mid});
}
left->update(x, y, k);
} else {
if (!right) {
right = new SegmentTree({mid, r});
}
right->update(x, y, k);
}
st->update(y, gcd((left ? left->simple_query(y) : 0), (right ? right->simple_query(y) : 0)));
}
}
ll query(int lx, int rx, int ly, int ry) {
if (l >= rx || lx >= r) {
return 0;
} else if (lx <= l && r <= rx) {
if (!st) {
return 0;
} else {
return st->query(ly, ry);
}
} else {
ll ans = 0;
if (left) {
ans = gcd(ans, left->query(lx, rx, ly, ry));
}
if (right) {
ans = gcd(ans, right->query(lx, rx, ly, ry));
}
return ans;
}
}
};
SegmentTree *root = nullptr;
void init(int R, int C) {
::R = R, ::C = C;
root = new SegmentTree({0, R});
}
void update(int P, int Q, ll K) {
root->update(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return root->query(P, U + 1, Q, V + 1);
}