Submission #945968

#TimeUsernameProblemLanguageResultExecution timeMemory
945968mansurGame (IOI13_game)C++17
37 / 100
13066 ms36448 KiB
#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; }
#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...