Submission #926406

#TimeUsernameProblemLanguageResultExecution timeMemory
926406myst6Game (IOI13_game)C++14
0 / 100
1 ms600 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; using ll = long long; struct Tree; struct Tree2; long long gcd2(long long X, long long Y); const int N = 15'000'000; map<int,int> treeV; int lptr[N], rptr[N]; ll val[N]; int nextfree = 1; int R, C; void update1(int idx, int v, int xl, int xr, ll delta) { if (v < xl || v > xr) return; if (xl == xr) { val[idx] = delta; } else { int xm = (xl + xr) / 2; if (v <= xm) { if (!lptr[idx]) lptr[idx] = nextfree++; update1(lptr[idx], v, xl, xm, delta); } else { if (!rptr[idx]) rptr[idx] = nextfree++; update1(rptr[idx], v, xm+1, xr, delta); } val[idx] = 0; if (lptr[idx]) val[idx] = gcd2(val[idx], val[lptr[idx]]); if (rptr[idx]) val[idx] = gcd2(val[idx], val[rptr[idx]]); } } ll query1(int idx, int l, int r, int xl, int xr) { if (l > r) return 0; if (l == xl && r == xr) { return val[idx]; } else { int xm = (xl + xr) / 2; ll ans = 0; if (lptr[idx]) ans = gcd2(ans, query1(lptr[idx], l, min(r, xm), xl, xm)); if (rptr) ans = gcd2(ans, query1(rptr[idx], max(l, xm+1), r, xm+1, xr)); return ans; } } void update2(int idx, int v, int w, int xl, int xr, ll delta) { if (v < xl || v > xr) return; ll delta2 = query1(treeV[w], xl, xr, 0, R-1); if (!val[idx]) val[idx] = nextfree++; update1(val[idx], w, 0, C-1, delta2); if (xl != xr) { int xm = (xl + xr) / 2; if (v <= xm) { if (!lptr[idx]) lptr[idx] = nextfree++; update2(lptr[idx], v, w, xl, xm, delta); } else { if (!rptr[idx]) rptr[idx] = nextfree++; update2(rptr[idx], v, w, xm+1, xr, delta); } } } ll query2(int idx, int l, int r, int l2, int r2, int xl, int xr) { if (l > r) return 0; if (l == xl && r == xr) { if (!val[idx]) return 0; return query1(val[idx], l2, r2, 0, C-1); } else { int xm = (xl + xr) / 2; ll ans = 0; if (lptr[idx]) ans = gcd2(ans, query2(lptr[idx], l, min(r, xm), l2, r2, xl, xm)); if (rptr[idx]) ans = gcd2(ans, query2(rptr[idx], max(l, xm+1), r, l2, r2, xm+1, xr)); return ans; } } 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; } void init(int _R, int _C) { R = _R; C = _C; } void update(int P, int Q, long long K) { if (treeV.count(Q) == 0) treeV[Q] = nextfree++; update1(treeV[Q], P, 0, R-1, K); update2(0, P, Q, 0, R-1, K); } long long calculate(int P, int Q, int U, int V) { return query2(0, P, U, Q, V, 0, R-1); }
#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...