Submission #261110

#TimeUsernameProblemLanguageResultExecution timeMemory
261110SamAndGame (IOI13_game)C++17
80 / 100
9308 ms256000 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; #define m_p make_pair #define fi first #define se second #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() typedef long long ll; const int T = 22003 * 30 * 30; long long gcd(long long X, long long Y) { long long tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } int R, C; map<pair<int, int>, ll> mp; int zy; int uly[T / 4 * 3], ury[T / 4 * 3]; ll g[T / 4 * 3]; int zx; int uy[T / 30]; int ulx[T / 30], urx[T / 30]; void ubdy(int tlx, int trx, int tly, int try_, int x, int y, ll k, int posyl, int posyr, int posy) { if (trx - tlx + 1 <= 3 && try_ - tly + 1 <= 3) { g[posy] = 0; for (int i = tlx; i <= trx; ++i) { for (int j = tly; j <= try_; ++j) { if (mp.find(m_p(i, j)) != mp.end()) g[posy] = gcd(g[posy], mp[m_p(i, j)]); } } return; } if (tly == try_) { if (tlx == trx) { g[posy] = k; return; } g[posy] = 0; int m = (tlx + trx) / 2; if (m - tlx + 1 <= 3) { for (int i = tlx; i <= m; ++i) { if (mp.find(m_p(i, tly)) != mp.end()) g[posy] = gcd(g[posy], mp[m_p(i, tly)]); } } else g[posy] = gcd(g[posy], g[posyl]); if (trx - m <= 3) { for (int i = m + 1; i <= trx; ++i) { if (mp.find(m_p(i, tly)) != mp.end()) g[posy] = gcd(g[posy], mp[m_p(i, tly)]); } } else g[posy] = gcd(g[posy], g[posyr]); return; } int m = (tly + try_) / 2; if (y <= m) { if (!uly[posy]) uly[posy] = ++zy; ubdy(tlx, trx, tly, m, x, y, k, uly[posyl], uly[posyr], uly[posy]); } else { if (!ury[posy]) ury[posy] = ++zy; ubdy(tlx, trx, m + 1, try_, x, y, k, ury[posyl], ury[posyr], ury[posy]); } g[posy] = gcd(g[uly[posy]], g[ury[posy]]); } void ubdx(int tlx, int trx, int x, int y, ll k, int posx) { if (tlx == trx) { if (!uy[posx]) uy[posx] = ++zy; ubdy(tlx, trx, 0, C - 1, x, y, k, 0, 0, uy[posx]); return; } int m = (tlx + trx) / 2; if (x <= m) { if (!ulx[posx]) ulx[posx] = ++zx; ubdx(tlx, m, x, y, k, ulx[posx]); } else { if (!urx[posx]) urx[posx] = ++zx; ubdx(m + 1, trx, x, y, k, urx[posx]); } if (!uy[posx]) uy[posx] = ++zy; ubdy(tlx, trx, 0, C - 1, x, y, k, uy[ulx[posx]], uy[urx[posx]], uy[posx]); } ll qryy(int tlx, int trx, int tly, int try_, int ly, int ry, int posy) { if (ly > ry) return 0; //if (posy == 0) // return 0; if (tly == ly && try_ == ry) { if (trx - tlx + 1 <= 3 && try_ - tly + 1 <= 3) { ll g = 0; for (int i = tlx; i <= trx; ++i) { for (int j = tly; j <= try_; ++j) { if (mp.find(m_p(i, j)) != mp.end()) g = gcd(g, mp[m_p(i, j)]); } } return g; } return g[posy]; } int m = (tly + try_) / 2; return gcd(qryy(tlx, trx, tly, m, ly, min(m, ry), uly[posy]), qryy(tlx, trx, m + 1, try_, max(m + 1, ly), ry, ury[posy])); } ll qryx(int tlx, int trx, int lx, int rx, int ly, int ry, int posx) { if (lx > rx) return 0; if (posx == 0) return 0; if (tlx == lx && trx == rx) { return qryy(tlx, trx, 0, C - 1, ly, ry, uy[posx]); } int m = (tlx + trx) / 2; return gcd(qryx(tlx, m, lx, min(m, rx), ly, ry, ulx[posx]), qryx(m + 1, trx, max(m + 1, lx), rx, ly, ry, urx[posx])); } void init(int R, int C) { ::R = R; ::C = C; ++zx; } void update(int P, int Q, long long K) { mp[m_p(P, Q)] = K; ubdx(0, R - 1, P, Q, K, 1); } long long calculate(int P, int Q, int U, int V) { return qryx(0, R - 1, P, U, Q, V, 1); }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
#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...