oj.uz

Submission #37983

# Submission time Handle Problem Language Result Execution time Memory
37983 2017-12-29T21:15:42 Z alenam0161 Game (IOI13_game) C++14
10 / 100
 13000 ms 197332 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[5000 * 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);
}
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();
	//	cout << x << " " << y << endl;
	//	cout << nlx << " " << nly << " " << nrx << " " << nry << endl;
	//	cout << "level" << endl;
	if (nlx == nrx&&nry == nly) {
		t->val = val;
		return;
	}
	int mx = (nlx + nrx) / 2;
	int my = (nly + nry) / 2;
	// ldown
	if (in_(nlx, nly, mx, my, x, y))updatequard(x, y, val, t->ldown, nlx, nly, mx, my);
	// lup
	else if (in_(mx + 1, nly, nrx, my, x, y))updatequard(x, y, val, t->lup, mx + 1, nly, nrx, my);
	// rdown
	else if (in_(nlx, my + 1, mx, nry, x, y))updatequard(x, y, val, t->rdown, nlx, my + 1, mx, nry);
	//rup
	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);
	//	cout << "hi" << endl;
}
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;
	//	cout << llx << " " << lly << " " << rrx << " " << rry << " " << nlx << " " << nly << " " << nrx << " " << nry << endl;
	int mx = (nlx + nrx) / 2;
	int my = (nly + nry) / 2;
	long long cur = 0;
	// ldown
	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));
	// lup
	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));
	// rdown
	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));
	//rup
	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 197332 KB Output is correct
2 Correct 19 ms 197332 KB Output is correct
3 Correct 29 ms 197332 KB Output is correct
4 Correct 16 ms 197332 KB Output is correct
5 Correct 0 ms 197332 KB Output is correct
6 Correct 16 ms 197332 KB Output is correct
7 Correct 13 ms 197332 KB Output is correct
8 Correct 23 ms 197332 KB Output is correct
9 Correct 29 ms 197332 KB Output is correct
10 Correct 23 ms 197332 KB Output is correct
11 Correct 29 ms 197332 KB Output is correct
12 Correct 19 ms 197332 KB Output is correct

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 197332 KB Output is correct
2 Correct 19 ms 197332 KB Output is correct
3 Correct 16 ms 197332 KB Output is correct
4 Correct 29 ms 197332 KB Output is correct
5 Correct 0 ms 197332 KB Output is correct
6 Correct 16 ms 197332 KB Output is correct
7 Correct 26 ms 197332 KB Output is correct
8 Correct 29 ms 197332 KB Output is correct
9 Correct 33 ms 197332 KB Output is correct
10 Correct 16 ms 197332 KB Output is correct
11 Correct 33 ms 197332 KB Output is correct
12 Correct 8206 ms 197332 KB Output is correct
13 Execution timed out 13000 ms 197332 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 197332 KB Output is correct
2 Correct 23 ms 197332 KB Output is correct
3 Correct 19 ms 197332 KB Output is correct
4 Correct 29 ms 197332 KB Output is correct
5 Correct 0 ms 197332 KB Output is correct
6 Correct 26 ms 197332 KB Output is correct
7 Correct 29 ms 197332 KB Output is correct
8 Correct 16 ms 197332 KB Output is correct
9 Correct 26 ms 197332 KB Output is correct
10 Correct 9 ms 197332 KB Output is correct
11 Correct 23 ms 197332 KB Output is correct
12 Execution timed out 13000 ms 197332 KB Execution timed out
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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