Submission #2912

#TimeUsernameProblemLanguageResultExecution timeMemory
2912asteinGame (IOI13_game)C++98
37 / 100
13000 ms7280 KiB
#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; 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; } 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;*/ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...