Submission #2910

#	Time	Username	Problem	Language	Result	Execution time	Memory
2910		astein	Game (IOI13_game)	C++98	37 / 100	13000 ms	7664 KiB

game

#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);
}

long long gcd(long long a, long long b) {
  if (a == 0 && b == 0) return 0;
  if (a == 0) return b;
  if (b == 0) return a;
  long long c = a % b;
  while (c) {
    a = b, b = c, c = a % b;
  }
  return b;
}

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 = gcd(next->lu->value, g);
    if (next->ru) g = gcd(next->ru->value, g);
    if (next->ld) g = gcd(next->ld->value, g);
    if (next->rd) g = gcd(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 calculate(int x1, int y1, int x2, int y2) {
  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 = gcd(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;
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20