| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 30035 | cdemirer | Game (IOI13_game) | C++14 | 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>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int R, C;
typedef struct Node_o_ {
int l, r;
int inner;
ll val;
} Node_o;
typedef struct Node_i_ {
int l, r;
ll val;
} Node_i;
#define oleft(x) (rez_o[(x)].l)
#define oright(x) (rez_o[(x)].r)
#define ileft(x) (rez_i[(x)].l)
#define iright(x) (rez_i[(x)].r)
const int MAXN = 1073741823;
Node_o rez_o[700000];
int roc = 1;
Node_i rez_i[21000000];
int ric = 1;
int root;
int createNode_o() {
rez_o[roc].l = rez_o[roc].r = rez_o[roc].inner = rez_o[roc].val = 0;
return roc++;
}
int createNode_i() {
rez_i[ric].l = rez_i[ric].r = rez_i[ric].val = 0;
return ric++;
}
ll get_i(int x, int l, int r, int cl, int cr) {
int mid = (cl+cr)/2;
if (l == cl && r == cr) return rez_i[x].val;
else if (l > mid) {
if (!iright(x)) return 0;
return get_i(iright(x), l, r, mid+1, cr);
}
else if (r <= mid) {
if (!ileft(x)) return 0;
return get_i(ileft(x), l, r, cl, mid);
}
else {
ll a, b;
if (!ileft(x)) a = 0;
else a = get_i(ileft(x), l, mid, cl, mid);
if (!iright(x)) b = 0;
else b = get_i(iright(x), mid+1, r, mid+1, cr);
return gcd2(a, b);
}
}
ll get_o(int x, int l, int r, int cl, int cr, int li, int ri) {
int mid = (cl+cr)/2;
if (l == cl && r == cr) {
if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
return get_i(rez_o[x].inner, li, ri, 0, MAXN);
}
else if (l > mid) {
if (!oright(x)) return 0;
return get_o(oright(x), l, r, mid+1, cr, li, ri);
}
else if (r <= mid) {
if (!oleft(x)) return 0;
return get_o(oleft(x), l, r, cl, mid, li, ri);
}
else {
ll a, b;
if (!oleft(x)) a = 0;
else a = get_o(oleft(x), l, mid, cl, mid, li, ri);
if (!oright(x)) b = 0;
else b = get_o(oright(x), mid+1, r, mid+1, cr, li, ri);
return gcd2(a, b);
}
}
void update_i(int x, int p, int cl, int cr, ll u) {
int mid = (cl+cr)/2;
if (p == cl && p == cr) {
rez_i[x].val = u;
}
else if (p > mid) {
if (!iright(x)) iright(x) = createNode_i();
update_i(iright(x), p, mid+1, cr, u);
rez_i[x].val = gcd2(rez_i[ileft(x)].val, rez_i[iright(x)].val);
}
else if (p <= mid) {
if (!ileft(x)) ileft(x) = createNode_i();
update_i(ileft(x), p, cl, mid, u);
rez_i[x].val = gcd2(rez_i[ileft(x)].val, rez_i[iright(x)].val);
}
}
void update_o(int x, int po, int pi, int cl, int cr, ll u) {
int mid = (cl+cr)/2;
if (po == cl && po == cr) {
if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
update_i(rez_o[x].inner, pi, 0, MAXN, u);
}
else if (po > mid) {
if (!oright(x)) oright(x) = createNode_o();
update_o(oright(x), po, pi, mid+1, cr, u);
ll nv = gcd2(get_i(rez_o[oleft(x)].inner, pi, pi, 0, MAXN), get_i(rez_o[oright(x)].inner, pi, pi, 0, MAXN));
if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
update_i(rez_o[x].inner, pi, 0, MAXN, nv);
}
else if (po <= mid) {
if (!oleft(x)) oleft(x) = createNode_o();
update_o(oleft(x), po, pi, cl, mid, u);
ll nv = gcd2(get_i(rez_o[oleft(x)].inner, pi, pi, 0, MAXN), get_i(rez_o[oright(x)].inner, pi, pi, 0, MAXN));
if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
update_i(rez_o[x].inner, pi, 0, MAXN, nv);
}
}
void init(int _R, int _C) {
R = _R;
C = _C;
root = createNode_o();
}
void update(int P, int Q, long long K) {
update_o(root, P, Q, 0, MAXN, K);
}
long long calculate(int P, int Q, int U, int V) {
return get_o(root, P, U, 0, MAXN, Q, V);
}