oj.uz

Submission #1090390

# Submission time Handle Problem Language Result Execution time Memory
1090390 2024-09-18T10:30:31 Z vjudge1 Game (IOI13_game) C++17
63 / 100
 1082 ms 138692 KB 
#include "game.h"
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;

ll gcd2(ll X, ll Y) {
	ll tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

vector <vector <ll>> sgt;
int Rs, Cs;

void init(int R, int C) {
	Rs = 1 << (int(ceil(log2(R))));
	Cs = 1 << (int(ceil(log2(C))));
	Rs--; Cs--;
	sgt.assign(2 * Rs + 1, vector<ll>(2 * Cs + 1, 0));
}

void update(int P, int Q, ll K) {
	int row = P + Rs, col = Q + Cs;
	sgt[row][col] = K;
	while (col) {
		col = (col - 1) / 2;
		sgt[row][col] = gcd2(sgt[row][2 * col + 1], sgt[row][2 * col + 2]);
	}
	while (row) {
		row = (row - 1) / 2;
		col = Q + Cs;
		sgt[row][col] = gcd2(sgt[2 * row + 1][col], sgt[2 * row + 2][col]);
		while (col) {
			col = (col - 1) / 2;
			sgt[row][col] = gcd2(sgt[row][2 * col + 1], sgt[row][2 * col + 2]);
		}
	}
}

ll sgtget(int row, int l, int r, int node, int cl, int cr) {
	if (r < cl || cr < l) return 0;
	if (l <= cl && cr <= r) return sgt[row][node];
	int cm = (cl + cr) / 2;
	return gcd2(sgtget(row, l, r, 2 * node + 1, cl, cm), sgtget(row, l, r, 2 * node + 2, cm + 1, cr));
}

ll sgtget2(int rl, int rr, int l, int r, int node, int cl, int cr) {
	if (rr < cl || cr < rl) return 0;
	if (rl <= cl && cr <= rr) return sgtget(node, l, r, 0, 0, Cs);
	int cm = (cl + cr) / 2;
	return gcd2(sgtget2(rl, rr, l, r, 2 * node + 1, cl, cm), sgtget2(rl, rr, l, r, 2 * node + 2, cm + 1, cr));
}

ll calculate(int P, int Q, int U, int V) {
	return sgtget2(P, U, Q, V, 0, 0, Rs);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 395 ms 72612 KB Output is correct
5 Correct 288 ms 72268 KB Output is correct
6 Correct 398 ms 69636 KB Output is correct
7 Correct 440 ms 69456 KB Output is correct
8 Correct 351 ms 69848 KB Output is correct
9 Correct 402 ms 69452 KB Output is correct
10 Correct 376 ms 69196 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 912 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 668 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct
11 Correct 0 ms 860 KB Output is correct
12 Correct 685 ms 41292 KB Output is correct
13 Correct 830 ms 37712 KB Output is correct
14 Correct 504 ms 137052 KB Output is correct
15 Correct 933 ms 136840 KB Output is correct
16 Correct 252 ms 136524 KB Output is correct
17 Correct 929 ms 137876 KB Output is correct
18 Correct 1027 ms 138064 KB Output is correct
19 Correct 1082 ms 138128 KB Output is correct
20 Correct 1010 ms 137688 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 936 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 0 ms 860 KB Output is correct
12 Correct 350 ms 72372 KB Output is correct
13 Correct 282 ms 72268 KB Output is correct
14 Correct 367 ms 69708 KB Output is correct
15 Correct 386 ms 69512 KB Output is correct
16 Correct 339 ms 69796 KB Output is correct
17 Correct 388 ms 69584 KB Output is correct
18 Correct 356 ms 69180 KB Output is correct
19 Correct 628 ms 41456 KB Output is correct
20 Correct 780 ms 37680 KB Output is correct
21 Correct 510 ms 136888 KB Output is correct
22 Correct 960 ms 136784 KB Output is correct
23 Correct 230 ms 136532 KB Output is correct
24 Correct 874 ms 137792 KB Output is correct
25 Correct 991 ms 137940 KB Output is correct
26 Correct 981 ms 138692 KB Output is correct
27 Correct 929 ms 137660 KB Output is correct
28 Runtime error 1 ms 344 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 367 ms 72392 KB Output is correct
13 Correct 303 ms 72388 KB Output is correct
14 Correct 415 ms 69708 KB Output is correct
15 Correct 404 ms 69580 KB Output is correct
16 Correct 371 ms 69964 KB Output is correct
17 Correct 389 ms 69452 KB Output is correct
18 Correct 360 ms 69192 KB Output is correct
19 Correct 631 ms 41392 KB Output is correct
20 Correct 841 ms 37876 KB Output is correct
21 Correct 512 ms 137044 KB Output is correct
22 Correct 976 ms 136872 KB Output is correct
23 Correct 225 ms 136532 KB Output is correct
24 Correct 824 ms 137948 KB Output is correct
25 Correct 943 ms 138184 KB Output is correct
26 Correct 997 ms 138232 KB Output is correct
27 Correct 1014 ms 137548 KB Output is correct
28 Runtime error 2 ms 344 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -