제출 #945905

#제출 시각아이디문제언어결과실행 시간메모리
945905mansur게임 (IOI13_game)C++17
10 / 100
13098 ms194592 KiB
#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 = 2e3 + 5; int n, m, lg[N]; ll vl[N][N], up[N][N][6]; 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 k = lg[r - l + 1], p = l; ll res = 0; while (true) { res = gcd2(res, up[R][p][k]); p += (1 << (2 * k)); if (p > r) break; p = min(p, r - (1 << (2 * k)) + 1); } return res; } void bld(int R) { for (int k = 0; k < 6; k++) { for (int i = 0; i < m - (1 << k) + 1; i++) { if (k) { int v = (1 << (2 * k - 2)); up[R][i][k] = gcd2(up[R][i][k - 1], up[R][i + v][k - 1]); up[R][i][k] = gcd2(up[R][i][k], up[R][i + 2 * v][k - 1]); up[R][i][k] = gcd2(up[R][i][k], up[R][i + 3 * v][k - 1]); }else up[R][i][k] = vl[R][i]; } } } void init(int R, int C) { n = R, m = C; lg[0] = -1; for (int i = 1; i <= m; i++) lg[i] = lg[i / 4] + 1; } void update(int P, int Q, ll K) { vl[P][Q] = K; bld(P); } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...