oj.uz

Submission #798918

# Submission time Handle Problem Language Result Execution time Memory
798918 2023-07-31T07:11:05 Z QwertyPi Game (IOI13_game) C++14
100 / 100
 2204 ms 81980 KB 
#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);
}

Compilation message

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.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 429 ms 9304 KB Output is correct
5 Correct 271 ms 9628 KB Output is correct
6 Correct 328 ms 6504 KB Output is correct
7 Correct 360 ms 6092 KB Output is correct
8 Correct 254 ms 4788 KB Output is correct
9 Correct 346 ms 6228 KB Output is correct
10 Correct 333 ms 5828 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 633 ms 12468 KB Output is correct
13 Correct 1144 ms 5924 KB Output is correct
14 Correct 183 ms 1840 KB Output is correct
15 Correct 1232 ms 7052 KB Output is correct
16 Correct 148 ms 10956 KB Output is correct
17 Correct 500 ms 7212 KB Output is correct
18 Correct 828 ms 11200 KB Output is correct
19 Correct 725 ms 11304 KB Output is correct
20 Correct 650 ms 10728 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 393 ms 9360 KB Output is correct
13 Correct 271 ms 9580 KB Output is correct
14 Correct 331 ms 6468 KB Output is correct
15 Correct 362 ms 6160 KB Output is correct
16 Correct 240 ms 4776 KB Output is correct
17 Correct 349 ms 6224 KB Output is correct
18 Correct 308 ms 5832 KB Output is correct
19 Correct 629 ms 12460 KB Output is correct
20 Correct 1121 ms 5960 KB Output is correct
21 Correct 189 ms 1976 KB Output is correct
22 Correct 1248 ms 7176 KB Output is correct
23 Correct 153 ms 10880 KB Output is correct
24 Correct 505 ms 7096 KB Output is correct
25 Correct 841 ms 11176 KB Output is correct
26 Correct 717 ms 11188 KB Output is correct
27 Correct 672 ms 10508 KB Output is correct
28 Correct 318 ms 43140 KB Output is correct
29 Correct 975 ms 45272 KB Output is correct
30 Correct 1666 ms 35300 KB Output is correct
31 Correct 1494 ms 28584 KB Output is correct
32 Correct 251 ms 10212 KB Output is correct
33 Correct 337 ms 10724 KB Output is correct
34 Correct 193 ms 39116 KB Output is correct
35 Correct 623 ms 26856 KB Output is correct
36 Correct 1224 ms 43208 KB Output is correct
37 Correct 963 ms 43444 KB Output is correct
38 Correct 929 ms 42800 KB Output is correct
39 Correct 774 ms 35656 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 384 ms 8476 KB Output is correct
13 Correct 255 ms 8792 KB Output is correct
14 Correct 323 ms 5652 KB Output is correct
15 Correct 360 ms 5328 KB Output is correct
16 Correct 274 ms 4056 KB Output is correct
17 Correct 356 ms 5460 KB Output is correct
18 Correct 319 ms 5020 KB Output is correct
19 Correct 608 ms 11696 KB Output is correct
20 Correct 1101 ms 5104 KB Output is correct
21 Correct 181 ms 1160 KB Output is correct
22 Correct 1220 ms 6352 KB Output is correct
23 Correct 153 ms 10064 KB Output is correct
24 Correct 501 ms 6516 KB Output is correct
25 Correct 803 ms 10492 KB Output is correct
26 Correct 696 ms 10572 KB Output is correct
27 Correct 635 ms 9976 KB Output is correct
28 Correct 320 ms 43272 KB Output is correct
29 Correct 899 ms 45340 KB Output is correct
30 Correct 1639 ms 35112 KB Output is correct
31 Correct 1492 ms 28400 KB Output is correct
32 Correct 252 ms 10128 KB Output is correct
33 Correct 352 ms 10704 KB Output is correct
34 Correct 193 ms 39112 KB Output is correct
35 Correct 619 ms 26848 KB Output is correct
36 Correct 1167 ms 43308 KB Output is correct
37 Correct 955 ms 43424 KB Output is correct
38 Correct 902 ms 42856 KB Output is correct
39 Correct 420 ms 81020 KB Output is correct
40 Correct 1417 ms 81980 KB Output is correct
41 Correct 2204 ms 67128 KB Output is correct
42 Correct 1999 ms 52424 KB Output is correct
43 Correct 359 ms 76728 KB Output is correct
44 Correct 312 ms 10700 KB Output is correct
45 Correct 785 ms 35608 KB Output is correct
46 Correct 1671 ms 80844 KB Output is correct
47 Correct 1664 ms 80920 KB Output is correct
48 Correct 1589 ms 80504 KB Output is correct
49 Correct 1 ms 212 KB Output is correct