oj.uz

Submission #1090380

# Submission time Handle Problem Language Result Execution time Memory
1090380 2024-09-18T09:57:48 Z vjudge1 Game (IOI13_game) C++17
37 / 100
 13000 ms 29276 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 Cs;

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

void update(int P, int Q, ll K) {
	int node = Q + Cs;
	sgt[P][node] = K;
	while (node) {
		node = (node - 1) / 2;
		sgt[P][node] = gcd2(sgt[P][2 * node + 1], sgt[P][2 * node + 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 calculate(int P, int Q, int U, int V) {
	ll r = 0;
	for (int i = P; i <= U; i++) {
		r = gcd2(r, sgtget(i, Q, V, 0, 0, Cs));
	}
	return r;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 420 KB Output is correct
4 Correct 594 ms 29180 KB Output is correct
5 Correct 393 ms 29004 KB Output is correct
6 Correct 466 ms 26444 KB Output is correct
7 Correct 457 ms 26224 KB Output is correct
8 Correct 376 ms 26700 KB Output is correct
9 Correct 487 ms 26444 KB Output is correct
10 Correct 400 ms 26124 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Execution timed out 13095 ms 19856 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 579 ms 29276 KB Output is correct
13 Correct 391 ms 29056 KB Output is correct
14 Correct 452 ms 26520 KB Output is correct
15 Correct 457 ms 26308 KB Output is correct
16 Correct 369 ms 26700 KB Output is correct
17 Correct 482 ms 26440 KB Output is correct
18 Correct 422 ms 26004 KB Output is correct
19 Execution timed out 13035 ms 19928 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 624 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 571 ms 29260 KB Output is correct
13 Correct 386 ms 29076 KB Output is correct
14 Correct 442 ms 26448 KB Output is correct
15 Correct 434 ms 26248 KB Output is correct
16 Correct 370 ms 26676 KB Output is correct
17 Correct 454 ms 26376 KB Output is correct
18 Correct 390 ms 26048 KB Output is correct
19 Execution timed out 13102 ms 19796 KB Time limit exceeded
20 Halted 0 ms 0 KB -