oj.uz

Submission #945968

# Submission time Handle Problem Language Result Execution time Memory
945968 2024-03-14T09:12:28 Z mansur Game (IOI13_game) C++17
37 / 100
 13000 ms 36448 KB 
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#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;
vector<vector<ll>> t;

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 || !t[R][u]) 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;
    t.resize(n);
    for (int i = 0; i < n; i++) t[i].resize(4 * m);
}

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 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 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 604 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 632 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 520 ms 35668 KB Output is correct
5 Correct 313 ms 35956 KB Output is correct
6 Correct 403 ms 32596 KB Output is correct
7 Correct 444 ms 32348 KB Output is correct
8 Correct 336 ms 33360 KB Output is correct
9 Correct 420 ms 32492 KB Output is correct
10 Correct 378 ms 32460 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 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 600 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 560 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 13066 ms 34916 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 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 Correct 525 ms 35608 KB Output is correct
13 Correct 320 ms 36008 KB Output is correct
14 Correct 402 ms 32624 KB Output is correct
15 Correct 444 ms 32336 KB Output is correct
16 Correct 318 ms 33308 KB Output is correct
17 Correct 427 ms 32592 KB Output is correct
18 Correct 386 ms 32284 KB Output is correct
19 Execution timed out 13060 ms 34836 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 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 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 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 528 ms 35628 KB Output is correct
13 Correct 316 ms 36448 KB Output is correct
14 Correct 419 ms 32596 KB Output is correct
15 Correct 457 ms 32336 KB Output is correct
16 Correct 314 ms 33652 KB Output is correct
17 Correct 431 ms 32440 KB Output is correct
18 Correct 391 ms 32420 KB Output is correct
19 Execution timed out 13042 ms 34872 KB Time limit exceeded
20 Halted 0 ms 0 KB -