oj.uz

답안 #37986

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37986 2017-12-29T21:28:04 Z alenam0161 게임 (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);
}
int llx, lly, rrx, rry;
long long get( 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( t->ldown, nlx, nly, mx, my));
	if (in_rect(llx, lly, rrx, rry, mx + 1, nly, nrx, my))cur = gcd2(cur, get( t->lup, mx + 1, nly, nrx, my));
	if (in_rect(llx, lly, rrx, rry, nlx, my + 1, mx, nry))cur = gcd2(cur, get( t->rdown, nlx, my + 1, mx, nry));
	if (in_rect(llx, lly, rrx, rry, mx + 1, my + 1, nrx, nry))cur = gcd2(cur, get( t->rup, mx + 1, my + 1, nrx, nry));
	return cur;
}

long long calculate(int P, int Q, int U, int V) {
	llx = P; lly = Q; rrx = U; rry = V;
	return get(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

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 236392 KB Output is correct
2 Correct 23 ms 236392 KB Output is correct
3 Correct 19 ms 236392 KB Output is correct
4 Correct 16 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 29 ms 236392 KB Output is correct
7 Correct 19 ms 236392 KB Output is correct
8 Correct 19 ms 236392 KB Output is correct
9 Correct 46 ms 236392 KB Output is correct
10 Correct 29 ms 236392 KB Output is correct
11 Correct 13 ms 236392 KB Output is correct
12 Correct 33 ms 236392 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 236392 KB Output is correct
2 Correct 26 ms 236392 KB Output is correct
3 Correct 26 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

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 236392 KB Output is correct
2 Correct 19 ms 236392 KB Output is correct
3 Correct 23 ms 236392 KB Output is correct
4 Correct 19 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 43 ms 236392 KB Output is correct
7 Correct 49 ms 236392 KB Output is correct
8 Correct 33 ms 236392 KB Output is correct
9 Correct 16 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 Correct 7269 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

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 236392 KB Output is correct
2 Correct 26 ms 236392 KB Output is correct
3 Correct 33 ms 236392 KB Output is correct
4 Correct 29 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 23 ms 236392 KB Output is correct
7 Correct 26 ms 236392 KB Output is correct
8 Correct 19 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 26 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

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 236392 KB Output is correct
2 Correct 33 ms 236392 KB Output is correct
3 Correct 26 ms 236392 KB Output is correct
4 Correct 26 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 33 ms 236392 KB Output is correct
8 Correct 36 ms 236392 KB Output is correct
9 Correct 46 ms 236392 KB Output is correct
10 Correct 33 ms 236392 KB Output is correct
11 Correct 29 ms 236392 KB Output is correct
12 Execution timed out 13000 ms 236392 KB Execution timed out
13 Halted 0 ms 0 KB -