제출 #689618

#제출 시각아이디문제언어결과실행 시간메모리
689618Mamedov게임 (IOI13_game)C++17
80 / 100
3499 ms256000 KiB
#pragma GCC optimize ("O3") #include "game.h" #include <bits/stdc++.h> #define pii pair<int, int> #define piii pair<pii, int> #define vi vector<int> #define vvi vector<vi> #define vpii vector<pii> #define vvpii vector<vpii> #define f first #define s second #define oo 1000000001 #define eb emplace_back #define pb push_back #define mpr make_pair #define size(v) (int)v.size() #define ln '\n' #define ull unsigned long long #define ll long long #define all(v) v.begin(), v.end() using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MAXR = 1e9; const int MAXC = 1e9; const int MAX = 1e7; ll gcd(ll a, ll b) { if (!b) return a; else return gcd(b, a % b); } ll tree[MAX]; int L[MAX], R[MAX], root[MAX]; int nxtFree = 1; void update1D(int v, int l, int r, int pos, ll val) { if (l == r) { tree[v] = val; } else { int mid = (l + r) >> 1; if (pos <= mid) { if (!L[v]) L[v] = ++nxtFree; update1D(L[v], l, mid, pos, val); } else { if (!R[v]) R[v] = ++nxtFree; update1D(R[v], mid + 1, r, pos, val); } ll gcdL = 0, gcdR = 0; if (L[v]) gcdL = tree[L[v]]; if (R[v]) gcdR = tree[R[v]]; tree[v] = gcd(gcdL, gcdR); } } ll query1D(int v, int l, int r, int ql, int qr) { if (ql > r || l > qr) return 0; else if (ql <= l && r <= qr) return tree[v]; else { int mid = (l + r) >> 1; ll gcdL = 0, gcdR = 0; if (L[v]) gcdL = query1D(L[v], l, mid, ql, qr); if (R[v]) gcdR = query1D(R[v], mid + 1, r, ql, qr); return gcd(gcdL, gcdR); } } void update2D(int v, int l, int r, int posR, int posC, ll val) { if (l == r) { if (!root[v]) root[v] = ++nxtFree; update1D(root[v], 1, MAXC, posC, val); } else { int mid = (l + r) >> 1; if (posR <= mid) { if (!L[v]) L[v] = ++nxtFree; update2D(L[v], l, mid, posR, posC, val); } else { if (!R[v]) R[v] = ++nxtFree; update2D(R[v], mid + 1, r, posR, posC, val); } ll gcdL = 0, gcdR = 0; if (L[v]) gcdL = query1D(root[L[v]], 1, MAXC, posC, posC); if (R[v]) gcdR = query1D(root[R[v]], 1, MAXC, posC, posC); ll combinedVal = gcd(gcdL, gcdR); if (!root[v]) root[v] = ++nxtFree; update1D(root[v], 1, MAXC, posC, combinedVal); } } ll query2D(int v, int l, int r, int rowL, int rowR, int colL, int colR) { if (rowL > r || l > rowR) return 0; else if (rowL <= l && r <= rowR) { if (root[v]) return query1D(root[v], 1, MAXC, colL, colR); else return 0; } else { int mid = (l + r) >> 1; ll gcdL = 0, gcdR = 0; if (L[v]) gcdL = query2D(L[v], l, mid, rowL, rowR, colL, colR); if (R[v]) gcdR = query2D(R[v], mid + 1, r, rowL, rowR, colL, colR); return gcd(gcdL, gcdR); } } void init(int R, int C) { } void update(int P, int Q, ll K) { ++P; ++Q; update2D(1, 1, MAXR, P, Q, K); } ll calculate(int P, int Q, int U, int V) { ++P; ++Q; ++U; ++V; return query2D(1, 1, MAXR, P, U, Q, V); }
#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...