| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 578875 | Mazaalai | Robots (IOI13_robots) | 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>
#define LINE "--------------------\n"
#define pb push_back
using namespace std;
using ll = long long;
int ST = 1;
int ED = 1e9;
ll gcd(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct SegTree1D {
int hasOne, child[2];
ll val;
SegTree1D() {
hasOne = val = 0; // 0 means empty, -1 means not empty, hasOne > 0 means id
child[0] = child[1] = -1;
}
};
struct SegTree2D {
int child[2], ptr;
vector <SegTree1D> node;
SegTree2D() {
ptr = 1;
node.clear();
node.pb(SegTree1D());
child[0] = child[1] = -1;
}
void update2(int l, int r, int id, ll val, int head) {
if (node[head].hasOne == id || node[head].hasOne == 0) {
node[head].val = val;
// cout << "UPDATED1: " << "(" << l << "," << r << ") " << id << " " << val << '\n';
node[head].hasOne = id;
return;
}
if (node[head].child[0] == -1) {
node[head].child[0] = ptr++;
node.pb(SegTree1D());
node[head].child[1] = ptr++;
node.pb(SegTree1D());
}
int mid = (l+r)>>1;
if (node[head].hasOne > 0) {
int tmp = node[head].hasOne; node[head].hasOne = -1;
if (tmp <= mid) update2(l, mid, tmp, node[head].val, node[head].child[0]);
else update2(mid+1, r, tmp, node[head].val, node[head].child[1]);
}
if (id <= mid) update2(l, mid, id, val, node[head].child[0]);
else update2(mid+1, r, id, val, node[head].child[1]);
node[head].val = gcd(
node[ node[head].child[0] ].val,
node[ node[head].child[1] ].val
);
// cout << "LR : " << node[ node[head].child[0] ].val << ',' << node[ node[head].child[1] ].val << '\n';
// cout << "UPDATED2: " << "(" << l << "," << r << ") " << id << " " << node[head].val << '\n';
}
void update2(int id, ll val) {
update2(ST, ED, id, val, 0);
}
ll query(int l, int r, int L, int R, int head) {
if (l > R || L > r || node[head].hasOne == 0) return 0;
if (L <= node[head].hasOne && node[head].hasOne <= R) return node[head].val;
if (L <= l && r <= R) return node[head].val;
int mid = (l+r)>>1;
if (node[head].child[0] == -1) {
node[head].child[0] = ptr++;
node.pb(SegTree1D());
node[head].child[1] = ptr++;
node.pb(SegTree1D());
}
return gcd(
query(l, mid, L, R, node[head].child[0]),
query(mid+1, r, L, R, node[head].child[1])
);
}
ll query(int l, int r) {
return query(ST, ED, l, r, 0);
}
ll query(int id) {
return query(ST, ED, id, id, 0);
}
};
vector <SegTree2D> node;
int ptr, X1, X2, Y1, Y2;
ll val;
void update1(int l, int r, int head) { // match X
if (l == r) {
// cout <<"OPEN " << l << ',' << r << "\n";
node[head].update2(Y1, val);
// cout <<"CLOSE\n";
return;
}
if (node[head].child[0] == -1) {
node[head].child[0] = ptr++;
node.pb(SegTree2D());
node[head].child[1] = ptr++;
node.pb(SegTree2D());
}
int mid = (l+r)>>1;
if (X1 <= mid) {
update1(l, mid, node[head].child[0]);
} else {
update1(mid+1, r, node[head].child[1]);
}
ll tmp = gcd(
node[ node[head].child[0] ].query(Y1),
node[ node[head].child[1] ].query(Y1)
);
// cout <<"OPEN " << l << ',' << r << "\n";
node[head].update2(Y1, tmp);
// cout <<"CLOSE\n";
return;
}
ll query(int l, int r, int head) {
if (l > X2 || X1 > r) return 0;
if (X1 <= l && r <= X2) return node[head].query(Y1, Y2);
if (node[head].child[0] == -1) {
node[head].child[0] = ptr++;
node.pb(SegTree2D());
node[head].child[1] = ptr++;
node.pb(SegTree2D());
}
int mid = (l+r)>>1;
return gcd(
query(l, mid, head*2+1),
query(mid+1, r, head*2+2)
);
}
void init(int R, int C) {
ST = 1, ED = max(R, C);
ptr = 1;
node.pb(SegTree2D());
}
void update(int x, int y, ll K) {
x++, y++;
X1 = x;
Y1 = y;
val = K;
// cout << LINE;
// cout << "UPDATE: " << x << ' ' << y << ' ' << K << '\n';
update1(ST, ED, 0);
}
ll calculate(int x1, int y1, int x2, int y2) {
x1++, y1++, x2++, y2++;
X1 = x1;
Y1 = y1;
X2 = x2;
Y2 = y2;
// cout << "RES: ";
return query(ST, ED, 0);
// return 1;
}