제출 #798918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
798918		QwertyPi	게임 (IOI13_game)	C++14	100 / 100	2204 ms	81980 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

long long gcd2(long long X, long long Y) {
	return __gcd(X, Y);
}

struct y_node{
	y_node() : l(0), r(0), left(NULL), right(NULL), a(0LL) {};
	y_node(int l, int r) : l(l), r(r), left(NULL), right(NULL), a(0LL) {};
	int l, r;
	long long a = 0;
	y_node *left = 0, *right = 0;
};

struct x_node{
	long long a = 0;
	x_node *left = 0, *right = 0;
	y_node y_tree;
};
int R, C;

long long get(y_node *v){
	if(!v) return 0;
	return v->a; 
}

long long get(x_node *v){
	if(!v) return 0;
	return v->a;
}

x_node *root;
void update_y(int y, long long K, y_node *v){
	int ll = v->l, rr = v->r, m = (ll + rr) / 2;
	if(ll == rr){
		v->a = K;
		return;
	}
	
	y_node **child = &(y <= m ? v->left : v->right);
	if(*child == 0){
		*child = new y_node(y, y);
		(*child)->a = K;
	}else if((*child)->l <= y && y <= (*child)->r){
		update_y(y, K, *child);
	}else{
		do{
			if(y <= m) rr = m;
			else ll = m + 1;
			m = (ll + rr) / 2;
		}while((y <= m) == ((*child)->r <= m));
		y_node *ny = new y_node(ll, rr);
		if((*child)->r <= m) ny->left = *child;
		else ny->right = *child;
		*child = ny;
		update_y(y, K, *child);
	}
	v->a = gcd2(get(v->left), get(v->right));
}

long long calc_y(int qy1, int qy2, y_node *v){
	if(!v || qy1 > v->r || v->l > qy2) return 0;
	if(qy1 <= v->l && v->r <= qy2) return v->a;
	return gcd2(calc_y(qy1, qy2, v->left), calc_y(qy1, qy2, v->right));
}

void update_x(int x, int y, long long K, x_node *v, int x1 = 0, int x2 = R - 1){
	if(x1 == x2){
		if(v->y_tree.a == 0) v->y_tree = y_node(0, C - 1);
		update_y(y, K, &v->y_tree);
		return;
	}
	int xm = (x1 + x2) / 2;
	if(x <= xm){
		if(!v->left) v->left = new x_node();
		update_x(x, y, K, v->left, x1, xm);
	}else{
		if(!v->right) v->right = new x_node();
		update_x(x, y, K, v->right, xm + 1, x2);
	}
	long long A = gcd2(v->left ? calc_y(y, y, &v->left->y_tree) : 0, 
					   v->right ? calc_y(y, y, &v->right->y_tree) : 0);
	if(v->y_tree.a == 0) v->y_tree = y_node(0, C - 1);
	update_y(y, A, &v->y_tree);
}

long long calc_x(int qx1, int qx2, int qy1, int qy2, x_node *v, int x1 = 0, int x2 = R - 1){
	if(!v || qx1 > x2 || x1 > qx2) return 0;
	if(qx1 <= x1 && x2 <= qx2) return calc_y(qy1, qy2, &v->y_tree);
	int xm = (x1 + x2) / 2;
	long long a1 = 0, a2 = 0;
	if(v->left) a1 = calc_x(qx1, qx2, qy1, qy2, v->left, x1, xm);
	if(v->right) a2 = calc_x(qx1, qx2, qy1, qy2, v->right, xm + 1, x2);
	return gcd2(a1, a2);
}

void init(int R, int C) {
	root = new x_node(); ::R = R, ::C = C;
}

void update(int P, int Q, long long K) {
    update_x(P, Q, K, root);
}

long long calculate(int P, int Q, int U, int V) {
    return calc_x(P, U, Q, V, root);
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In constructor 'y_node::y_node()':
game.cpp:15:21: warning: 'y_node::right' will be initialized after [-Wreorder]
   15 |  y_node *left = 0, *right = 0;
      |                     ^~~~~
game.cpp:14:12: warning:   'long long int y_node::a' [-Wreorder]
   14 |  long long a = 0;
      |            ^
game.cpp:11:2: warning:   when initialized here [-Wreorder]
   11 |  y_node() : l(0), r(0), left(NULL), right(NULL), a(0LL) {};
      |  ^~~~~~
game.cpp: In constructor 'y_node::y_node(int, int)':
game.cpp:15:21: warning: 'y_node::right' will be initialized after [-Wreorder]
   15 |  y_node *left = 0, *right = 0;
      |                     ^~~~~
game.cpp:14:12: warning:   'long long int y_node::a' [-Wreorder]
   14 |  long long a = 0;
      |            ^
game.cpp:12:2: warning:   when initialized here [-Wreorder]
   12 |  y_node(int l, int r) : l(l), r(r), left(NULL), right(NULL), a(0LL) {};
      |  ^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20