| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 2911 | astein | Game (IOI13_game) | C++98 | 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 <cstring>
#include <queue>
#include <cstdio>
#include <cassert>
using namespace std;
struct Node {
Node *lu, *ld, *ru, *rd;
Node* parent;
int sx, sy, ex, ey;
long long value;
Node(int x1, int y1, int x2, int y2, long long v) : sx(x1), sy(y1), ex(x2), ey(y2), value(v) { lu = 0, ld = 0, ru = 0, rd = 0; }
};
Node* root;
void init(int R, int C) {
root = new Node(0, 0, R - 1, C - 1, 0);
}
void update(int x, int y, long long v) {
Node* next = root;
while (true) {
int sx = next->sx, sy = next->sy, ex = next->ex, ey = next->ey;
if (sx == ex && sy == ey && x == sx && y == sy) {
//printf("%d, %d - %d, %d : %lld\n", sx, sy, ex, ey, v);
next->value = v;
break;
}
int mx = (sx + ex) / 2;
int my = (sy + ey) / 2;
if (sx <= x && x <= mx) {
if (sy <= y && y <= my) {
// lu
if (!next->lu) {
Node* child = new Node(sx, sy, mx, my, 0);
child->parent = next;
next->lu = child;
}
next = next->lu;
} else {
// ru
if (!next->ru) {
Node* child = new Node(sx, my + 1, mx, ey, 0);
child->parent = next;
next->ru = child;
}
next = next->ru;
}
} else {
if (sy <= y && y <= my) {
// ld
if (!next->ld) {
Node* child = new Node(mx + 1, sy, ex, my, 0);
child->parent = next;
next->ld = child;
}
next = next->ld;
} else {
// rd
if (!next->rd) {
Node* child = new Node(mx + 1, my + 1, ex, ey, 0);
child->parent = next;
next->rd = child;
}
next = next->rd;
}
}
}
Node* up;
while (next != root) {
next = next->parent;
long long g = 0;
if (next->lu) g = gcd2(next->lu->value, g);
if (next->ru) g = gcd2(next->ru->value, g);
if (next->ld) g = gcd2(next->ld->value, g);
if (next->rd) g = gcd2(next->rd->value, g);
next->value = g;
//printf("%d, %d - %d, %d : %lld\n", next->sx, next->sy, next->ex, next->ey, next->value);
}
}
long long go(int x1, int y1, int x2, int y2, Node* now) {
long long g = 0;
if (x1 <= now->sx && y1 <= now->sy && now->ex <= x2 && now->ey <= y2) {
return now->value;
}
if (now->sx > x2 || now->sy > y2) return 0;
if (now->ex < x1 || now->ey < y1) return 0;
if (now->lu) g = gcd2(g, go(x1, y1, x2, y2, now->lu));
if (now->ld) g = gcd2(g, go(x1, y1, x2, y2, now->ld));
if (now->ru) g = gcd2(g, go(x1, y1, x2, y2, now->ru));
if (now->rd) g = gcd2(g, go(x1, y1, x2, y2, now->rd));
return g;
}
long long calculate(int x1, int y1, int x2, int y2) {
return go(x1, y1, x2, y2, root);
/* long long g = 0;
queue<Node*> Q;
Q.push(root);
long long g = 0;
while (!Q.empty()) {
Node* now = Q.front(); Q.pop();
if (x1 <= now->sx && y1 <= now->sy && now->ex <= x2 && now->ey <= y2) {
g = gcd2(now->value, g);
continue;
}
if (now->sx > x2) continue;
if (now->sy > y2) continue;
if (now->ex < x1) continue;
if (now->ey < y1) continue;
if (now->lu) Q.push(now->lu);
if (now->ld) Q.push(now->ld);
if (now->ru) Q.push(now->ru);
if (now->rd) Q.push(now->rd);
}
return g;*/
}
void clear(Node* now) {
queue<Node*> Q;
Q.push(now);
int numNode = 0;
while (!Q.empty()) {
now = Q.front(); Q.pop();
if (now->lu) Q.push(now->lu);
if (now->ld) Q.push(now->ld);
if (now->ru) Q.push(now->ru);
if (now->rd) Q.push(now->rd);
now->parent = 0;
numNode++;
delete now;
}
// printf("total memory = %d\n", numNode * sizeof(Node));
}