oj.uz

Submission #945966

# Submission time Handle Problem Language Result Execution time Memory
945966 2024-03-14T09:11:17 Z vjudge1 Game (IOI13_game) C++17
37 / 100
 13000 ms 40232 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 1 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 436 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 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 696 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 539 ms 40044 KB Output is correct
5 Correct 338 ms 40020 KB Output is correct
6 Correct 400 ms 37456 KB Output is correct
7 Correct 495 ms 36980 KB Output is correct
8 Correct 321 ms 37456 KB Output is correct
9 Correct 433 ms 37124 KB Output is correct
10 Correct 402 ms 36888 KB Output is correct
11 Correct 0 ms 344 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 1 ms 436 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 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 692 KB Output is correct
12 Execution timed out 13100 ms 37900 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 604 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 563 ms 40232 KB Output is correct
13 Correct 320 ms 39864 KB Output is correct
14 Correct 472 ms 37416 KB Output is correct
15 Correct 452 ms 37208 KB Output is correct
16 Correct 333 ms 37456 KB Output is correct
17 Correct 442 ms 37284 KB Output is correct
18 Correct 389 ms 36740 KB Output is correct
19 Execution timed out 13049 ms 38120 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 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 1 ms 604 KB Output is correct
7 Correct 1 ms 376 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 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 583 ms 39972 KB Output is correct
13 Correct 320 ms 40048 KB Output is correct
14 Correct 408 ms 37344 KB Output is correct
15 Correct 461 ms 37212 KB Output is correct
16 Correct 321 ms 37464 KB Output is correct
17 Correct 463 ms 37160 KB Output is correct
18 Correct 417 ms 36896 KB Output is correct
19 Execution timed out 13036 ms 37796 KB Time limit exceeded
20 Halted 0 ms 0 KB -