oj.uz

Submission #946274

# Submission time Handle Problem Language Result Execution time Memory
946274 2024-03-14T13:16:34 Z vjudge1 Game (IOI13_game) C++17
10 / 100
 13000 ms 22564 KB 
#include "game.h"
#include<bits/stdc++.h>

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 2001;

int n, m;
ll t[N][4 * N];

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;
}

ll get(int R, int l, int r, int u = 1, int tl = 0, int tr = m - 1) {
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return t[R][u];
	int m = (tl + tr) / 2;
	return gcd2(get(R, l, r, u * 2, tl, m), get(R, l, r, u * 2 + 1, m + 1, tr));
}

void upd(int R, int p, ll v, int u = 1, int tl = 0, int tr = m - 1) {
	if (tl == tr) {
		t[R][u] = v;
		return;
	}
	int m = (tl + tr) / 2;
	if (p <= m) upd(R, p, v, u * 2, tl, m);
	else upd(R, p, v, u * 2 + 1, m + 1, tr);
	t[R][u] = gcd2(t[R][u * 2], t[R][u * 2 + 1]);
}

void init(int R, int C) {
    n = R, m = C;
}

void update(int P, int Q, ll K) {
	upd(P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
	ll ans = 0;
	for (int i = P; i <= U; i++) {
		ans = gcd2(ans, get(i, Q, V));
	}
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 404 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
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 Incorrect 764 ms 6260 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 444 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 2744 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 1 ms 6592 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 4552 KB Output is correct
12 Execution timed out 13091 ms 22564 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 6496 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 6592 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Incorrect 741 ms 6256 KB Output isn't correct
13 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 6492 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 6588 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 4540 KB Output is correct
12 Incorrect 732 ms 6404 KB Output isn't correct
13 Halted 0 ms 0 KB -