oj.uz

Submission #2910

# Submission time Handle Problem Language Result Execution time Memory
2910 2013-08-03T09:40:57 Z astein Game (IOI13_game) C++
37 / 100
 13000 ms 7664 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1240 KB Output is correct
2 Correct 0 ms 1240 KB Output is correct
3 Correct 0 ms 1240 KB Output is correct
4 Correct 0 ms 1240 KB Output is correct
5 Correct 0 ms 1240 KB Output is correct
6 Correct 0 ms 1240 KB Output is correct
7 Correct 0 ms 1240 KB Output is correct
8 Correct 0 ms 1240 KB Output is correct
9 Correct 0 ms 1240 KB Output is correct
10 Correct 0 ms 1240 KB Output is correct
11 Correct 0 ms 1240 KB Output is correct
12 Correct 0 ms 1240 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1240 KB Output is correct
2 Correct 0 ms 1240 KB Output is correct
3 Correct 0 ms 1240 KB Output is correct
4 Correct 1580 ms 7420 KB Output is correct
5 Correct 1120 ms 7412 KB Output is correct
6 Correct 1012 ms 7664 KB Output is correct
7 Correct 1140 ms 7312 KB Output is correct
8 Correct 756 ms 4716 KB Output is correct
9 Correct 1088 ms 7664 KB Output is correct
10 Correct 1080 ms 7592 KB Output is correct
11 Correct 0 ms 1240 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1240 KB Output is correct
2 Correct 0 ms 1240 KB Output is correct
3 Correct 0 ms 1240 KB Output is correct
4 Correct 0 ms 1240 KB Output is correct
5 Correct 0 ms 1240 KB Output is correct
6 Correct 0 ms 1240 KB Output is correct
7 Correct 0 ms 1240 KB Output is correct
8 Correct 0 ms 1240 KB Output is correct
9 Correct 0 ms 1240 KB Output is correct
10 Correct 0 ms 1240 KB Output is correct
11 Correct 0 ms 1240 KB Output is correct
12 Correct 8376 ms 4536 KB Output is correct
13 Execution timed out 13000 ms 2736 KB Program timed out
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1240 KB Output is correct
2 Correct 0 ms 1240 KB Output is correct
3 Correct 0 ms 1240 KB Output is correct
4 Correct 0 ms 1240 KB Output is correct
5 Correct 0 ms 1240 KB Output is correct
6 Correct 0 ms 1240 KB Output is correct
7 Correct 0 ms 1240 KB Output is correct
8 Correct 0 ms 1240 KB Output is correct
9 Correct 0 ms 1240 KB Output is correct
10 Correct 0 ms 1240 KB Output is correct
11 Correct 0 ms 1240 KB Output is correct
12 Correct 1548 ms 7420 KB Output is correct
13 Correct 1128 ms 7412 KB Output is correct
14 Correct 988 ms 7664 KB Output is correct
15 Correct 1132 ms 7312 KB Output is correct
16 Correct 764 ms 4716 KB Output is correct
17 Correct 1068 ms 7664 KB Output is correct
18 Correct 1092 ms 7592 KB Output is correct
19 Correct 8380 ms 4536 KB Output is correct
20 Execution timed out 13000 ms 2736 KB Program timed out
21 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1240 KB Output is correct
2 Correct 0 ms 1240 KB Output is correct
3 Correct 0 ms 1240 KB Output is correct
4 Correct 0 ms 1240 KB Output is correct
5 Correct 0 ms 1240 KB Output is correct
6 Correct 0 ms 1240 KB Output is correct
7 Correct 0 ms 1240 KB Output is correct
8 Correct 0 ms 1240 KB Output is correct
9 Correct 0 ms 1240 KB Output is correct
10 Correct 0 ms 1240 KB Output is correct
11 Correct 0 ms 1240 KB Output is correct
12 Correct 1548 ms 7420 KB Output is correct
13 Correct 1120 ms 7412 KB Output is correct
14 Correct 972 ms 7664 KB Output is correct
15 Correct 1112 ms 7312 KB Output is correct
16 Correct 752 ms 4716 KB Output is correct
17 Correct 1072 ms 7664 KB Output is correct
18 Correct 1088 ms 7592 KB Output is correct
19 Correct 8352 ms 4536 KB Output is correct
20 Execution timed out 13000 ms 2736 KB Program timed out
21 Halted 0 ms 0 KB -