제출 #645706

#제출 시각아이디문제언어결과실행 시간메모리
645706abeker게임 (IOI13_game)C++17
63 / 100
5550 ms256000 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; typedef long long ll; typedef unordered_map <int, ll> umap; const int offset = 1 << 30; const int MAX_ROW = 6.7e5; int row_root; int l[MAX_ROW], r[MAX_ROW]; umap num[MAX_ROW]; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } void create_row(int &node) { static int sz; if (!node) node = ++sz; } void init(int R, int C) { create_row(row_root); } ll get(umap &ref, ll val) { return ref.find(val) == ref.end() ? 0 : ref[val]; } void update_col(umap &tour, umap &lft, umap &rig, int x, ll val) { x += offset; tour[x] = gcd(get(lft, x), get(rig, x)); if (!tour[x]) tour[x] = val; for (x /= 2; x; x /= 2) tour[x] = gcd(get(tour, 2 * x), get(tour, 2 * x + 1)); } void update_row(int x, int lo, int hi, int row, int col, ll val) { if (hi - lo > 1) { int mid = (lo + hi) / 2; if (row < mid) { create_row(l[x]); update_row(l[x], lo, mid, row, col, val); } else { create_row(r[x]); update_row(r[x], mid, hi, row, col, val); } } update_col(num[x], num[l[x]], num[r[x]], col, val); } void update(int p, int q, ll k) { update_row(row_root, 0, offset, p, q, k); } ll query_col(umap &tour, int x, int lo, int hi, int from, int to) { if (lo >= to || hi <= from || tour.find(x) == tour.end()) return 0; if (lo >= from && hi <= to) return tour[x]; int mid = (lo + hi) / 2; return gcd(query_col(tour, 2 * x, lo, mid, from, to), query_col(tour, 2 * x + 1, mid, hi, from, to)); } ll query_row(int x, int lo, int hi, int from, int to, int col1, int col2) { if (!x || lo >= to || hi <= from) return 0; if (lo >= from && hi <= to) return query_col(num[x], 1, 0, offset, col1, col2); int mid = (lo + hi) / 2; return gcd(query_row(l[x], lo, mid, from, to, col1, col2), query_row(r[x], mid, hi, from, to, col1, col2)); } ll calculate(int p, int q, int u, int v) { return query_row(row_root, 0, offset, p, u + 1, q, v + 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...