Submission #416719

#TimeUsernameProblemLanguageResultExecution timeMemory
416719TangentGame (IOI13_game)C++17
63 / 100
13077 ms59036 KiB
#include "game.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef vector<ll> vll; typedef vector<int> vii; typedef vector<vll> vvll; typedef vector<vii> vvii; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<pll> vpll; typedef vector<pii> vpii; typedef vector<vpll> vvpll; typedef vector<vpii> vvpii; #define ffor(i, a, b) for (ll i = a; i < b; i++) #define rep(i, n) ffor(i, 0, n) #define forin(x, a) for (auto &x: a) #define all(x) x.begin(), x.end() 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 r, c; unordered_map<ll, ll> t; ll gett(int y, int x) { ll k = 4 * r * y + x; if (t.find(k) == t.end()) { return 0; } return t[k]; } void sett(int y, int x, ll v) { ll k = 4 * r * y + x; if (v) { t[k] = v; } else { t.erase(k); } // cout << y << ' ' << x << ' ' << v << '\n'; } void init(int R, int C) { r = R; c = C; } void upd2(int y, int x, long long v, int y1, int y2, int x1, int x2, int yt, int xt) { if (y1 == y2) { if (x1 == x2) { sett(y, x, v); } else { sett(y, x, gcd2(gett(y, 2 * x), gett(y, 2 * x + 1))); } } else { int my = (y1 + y2) / 2; if (yt <= my) { upd2(y * 2, x, v, y1, my, x1, x2, yt, xt); } else { upd2(y * 2 + 1, x, v, my + 1, y2, x1, x2, yt, xt); } sett(y, x, gcd2(gett(y * 2, x), gett(y * 2 + 1, x))); } } void upd(int y, int x, long long v, int y1, int y2, int x1, int x2, int yt, int xt) { if (x1 != x2) { int mx = (x1 + x2) / 2; if (xt <= mx) { upd(y, x * 2, v, y1, y2, x1, mx, yt, xt); } else { upd(y, x * 2 + 1, v, y1, y2, mx + 1, x2, yt, xt); } } upd2(y, x, v, y1, y2, x1, x2, yt, xt); } void update(int P, int Q, long long K) { upd(1, 1, K, 0, c - 1, 0, r - 1, Q, P); } ll query(int y, int x, int y1, int y2, int x1, int x2, int yt1, int xt1, int yt2, int xt2) { if (x1 == xt1 && x2 == xt2) { if (y1 == yt1 && y2 == yt2) { return gett(y, x); } else { int my = (y1 + y2) / 2; ll res = 0; if (yt1 <= my) { res = gcd2(res, query(y * 2, x, y1, my, x1, x2, yt1, xt1, min(yt2, my), xt2)); } if (yt2 > my) { res = gcd2(res, query(y * 2 + 1, x, my + 1, y2, x1, x2, max(yt1, my + 1), xt1, yt2, xt2)); } return res; } } else { int mx = (x1 + x2) / 2; ll res = 0; if (xt1 <= mx) { res = gcd2(res, query(y, x * 2, y1, y2, x1, mx, yt1, xt1, yt2, min(xt2, mx))); } if (xt2 > mx) { res = gcd2(res, query(y, x * 2 + 1, y1, y2, mx + 1, x2, yt1, max(xt1, mx + 1), yt2, xt2)); } return res; } } long long calculate(int x1, int y1, int x2, int y2) { return query(1, 1, 0, c - 1, 0, r - 1, y1, x1, y2, x2); }
#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...