oj.uz

Submission #37985

# Submission time Handle Problem Language Result Execution time Memory
37985 2017-12-29T21:20:33 Z alenam0161 Game (IOI13_game) C++14
10 / 100
 13000 ms 236392 KB 
#include "game.h"
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = ((int)1 << 30) - 1;
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;
}
struct node {
	long long val;
	node *lup, *ldown, *rup, *rdown;
	node(long long q = 0) {
		val = q;
		lup = ldown = rup = rdown = NULL;
	}
};
node *root;
node* get_node() {
	static node T[6000 * 1000];
	static int counter = 0;
	return &T[counter++];
}
inline long long get_(node *t) {
	return t ? t->val : 0ll;
}
inline bool in_(int llx, int lly, int rrx, int rry, int nx, int ny) {
	return  (llx <= nx&&lly <= ny&&rrx >= nx&&rry >= ny);
}
inline bool in_rect(int llx, int lly, int rrx, int rry, int nlx, int nly, int nrx, int nry) {
	return (nrx < llx || nry < lly || rrx < nlx || rry < nly) ? 0 : 1;
}
void init(int R, int C) {
	/* ... */
}
void updatequard(int x, int y, long long val, node *&t, int nlx, int nly, int nrx, int nry) {
	if (!t)t = get_node();
	if (nlx == nrx&&nry == nly) {
		t->val = val;
		return;
	}
	int mx = (nlx + nrx) / 2;
	int my = (nly + nry) / 2;
	if (in_(nlx, nly, mx, my, x, y))updatequard(x, y, val, t->ldown, nlx, nly, mx, my);
	else if (in_(mx + 1, nly, nrx, my, x, y))updatequard(x, y, val, t->lup, mx + 1, nly, nrx, my);
	else if (in_(nlx, my + 1, mx, nry, x, y))updatequard(x, y, val, t->rdown, nlx, my + 1, mx, nry);
	else updatequard(x, y, val, t->rup, mx + 1, my + 1, nrx, nry);
	t->val = gcd2(
		gcd2(get_(t->ldown), get_(t->lup)),
		gcd2(get_(t->rdown), get_(t->rup))
	);
}
void update(int P, int Q, long long K) {
	updatequard(P, Q, K, root, 0, 0, N, N);
}
long long get(int llx, int lly, int rrx, int rry, node *t, int nlx, int nly, int nrx, int nry) {
	if (!t)return 0ll;
	if (in_(llx, lly, rrx, rry, nlx, nly) && in_(llx, lly, rrx, rry, nrx, nry))return t->val;
	int mx = (nlx + nrx) / 2;
	int my = (nly + nry) / 2;
	long long cur = 0;
	if (in_rect(llx, lly, rrx, rry, nlx, nly, mx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->ldown, nlx, nly, mx, my));
	if (in_rect(llx, lly, rrx, rry, mx + 1, nly, nrx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->lup, mx + 1, nly, nrx, my));
	if (in_rect(llx, lly, rrx, rry, nlx, my + 1, mx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->rdown, nlx, my + 1, mx, nry));
	if (in_rect(llx, lly, rrx, rry, mx + 1, my + 1, nrx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->rup, mx + 1, my + 1, nrx, nry));
	return cur;
}

long long calculate(int P, int Q, int U, int V) {
	return get(P, Q, U, V, root, 0, 0, N, N);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 236392 KB Output is correct
2 Correct 16 ms 236392 KB Output is correct
3 Correct 36 ms 236392 KB Output is correct
4 Correct 23 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 26 ms 236392 KB Output is correct
7 Correct 26 ms 236392 KB Output is correct
8 Correct 43 ms 236392 KB Output is correct
9 Correct 26 ms 236392 KB Output is correct
10 Correct 16 ms 236392 KB Output is correct
11 Correct 33 ms 236392 KB Output is correct
12 Correct 26 ms 236392 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 236392 KB Output is correct
2 Correct 43 ms 236392 KB Output is correct
3 Correct 33 ms 236392 KB Output is correct
4 Execution timed out 13000 ms 236392 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 236392 KB Output is correct
2 Correct 33 ms 236392 KB Output is correct
3 Correct 23 ms 236392 KB Output is correct
4 Correct 36 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 46 ms 236392 KB Output is correct
7 Correct 39 ms 236392 KB Output is correct
8 Correct 33 ms 236392 KB Output is correct
9 Correct 36 ms 236392 KB Output is correct
10 Correct 29 ms 236392 KB Output is correct
11 Correct 29 ms 236392 KB Output is correct
12 Correct 8343 ms 236392 KB Output is correct
13 Execution timed out 13000 ms 236392 KB Execution timed out
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 236392 KB Output is correct
2 Correct 33 ms 236392 KB Output is correct
3 Correct 16 ms 236392 KB Output is correct
4 Correct 33 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 26 ms 236392 KB Output is correct
7 Correct 29 ms 236392 KB Output is correct
8 Correct 9 ms 236392 KB Output is correct
9 Correct 33 ms 236392 KB Output is correct
10 Correct 23 ms 236392 KB Output is correct
11 Correct 39 ms 236392 KB Output is correct
12 Execution timed out 13000 ms 236392 KB Execution timed out
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 236392 KB Output is correct
2 Correct 33 ms 236392 KB Output is correct
3 Correct 46 ms 236392 KB Output is correct
4 Correct 36 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 19 ms 236392 KB Output is correct
7 Correct 29 ms 236392 KB Output is correct
8 Correct 36 ms 236392 KB Output is correct
9 Correct 36 ms 236392 KB Output is correct
10 Correct 23 ms 236392 KB Output is correct
11 Correct 16 ms 236392 KB Output is correct
12 Execution timed out 13000 ms 236392 KB Execution timed out
13 Halted 0 ms 0 KB -