oj.uz

Submission #2912

# Submission time Handle Problem Language Result Execution time Memory
2912 2013-08-03T09:59:07 Z astein Game (IOI13_game) C++
37 / 100
 13000 ms 7280 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;


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;*/
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 1332 ms 7016 KB Output is correct
5 Correct 700 ms 7016 KB Output is correct
6 Correct 1112 ms 7280 KB Output is correct
7 Correct 1304 ms 7280 KB Output is correct
8 Correct 768 ms 4508 KB Output is correct
9 Correct 1228 ms 7280 KB Output is correct
10 Correct 1048 ms 7280 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 7052 ms 4376 KB Output is correct
13 Execution timed out 13000 ms 2660 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 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 1316 ms 7016 KB Output is correct
13 Correct 724 ms 7016 KB Output is correct
14 Correct 1092 ms 7280 KB Output is correct
15 Correct 1292 ms 7280 KB Output is correct
16 Correct 772 ms 4508 KB Output is correct
17 Correct 1200 ms 7280 KB Output is correct
18 Correct 1044 ms 7280 KB Output is correct
19 Correct 7084 ms 4376 KB Output is correct
20 Execution timed out 13000 ms 2660 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 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 1308 ms 7016 KB Output is correct
13 Correct 724 ms 7016 KB Output is correct
14 Correct 1100 ms 7280 KB Output is correct
15 Correct 1280 ms 7280 KB Output is correct
16 Correct 760 ms 4508 KB Output is correct
17 Correct 1236 ms 7280 KB Output is correct
18 Correct 1068 ms 7280 KB Output is correct
19 Correct 7080 ms 4376 KB Output is correct
20 Execution timed out 13000 ms 2660 KB Program timed out
21 Halted 0 ms 0 KB -