제출 #963472

#제출 시각아이디문제언어결과실행 시간메모리
963472NValchanov게임 (IOI13_game)C++17
0 / 100
1 ms436 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; typedef long long ll; const ll MAXN = 2e3 + 10; long long gcd2(long long X, long long Y) { if(X == 0 && Y == 0) return 0; else if(X == 0 && Y != 0) return Y; else if(X != 0 && Y == 0) return X; long long tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } ll n,m; /// 2D SEGMENT TREE CODE struct segment_tree_2d { /// SEGMENT TREE CODE struct segment_tree { /// NODE CODE struct node { node *l; node *r; ll val; node() { val = 0; l = nullptr; r = nullptr; } node(ll _val) { val = _val; l = nullptr; r = nullptr; } }; node *root; segment_tree *l; segment_tree *r; segment_tree() { root = new node(); l = nullptr; r = nullptr; } void merge_nodes(node *tree) { if(tree -> l == nullptr) tree -> l = new node(); if(tree -> r == nullptr) tree -> r = new node(); tree -> val = gcd2(tree -> l -> val, tree -> r -> val); } void update(node *tree, ll left, ll right, ll pos, ll x) { if(tree == nullptr) return; if(left == right) { tree -> val = x; return; } ll mid = left + (right - left) / 2; if(pos <= mid) { update(tree -> l, left, mid, pos, x); } else { update(tree -> r, mid + 1, right, pos, x); } merge_nodes(tree); } ll query(node *tree, ll left, ll right, ll qleft, ll qright) { if(tree == nullptr) return 0LL; if(qright < left || right < qleft) return 0LL; if(qleft <= left && right <= qright) return tree -> val; ll mid = left + (right - left) / 2; ll Lnode = query(tree -> l, left, mid, qleft, qright); ll Rnode = query(tree -> r, mid + 1, right, qleft, qright); return gcd2(Lnode, Rnode); } void update(ll pos, ll x) { update(root, 0, m - 1, pos, x); } ll query(ll qleft, ll qright) { return query(root, 0, m - 1, qleft, qright); } }; segment_tree *root; segment_tree_2d() { root = new segment_tree(); } void merge(segment_tree *tree, ll pos) { ll Lnode = tree -> l -> query(pos, pos); ll Rnode = tree -> r -> query(pos, pos); tree -> update(pos, gcd2(Lnode, Rnode)); } void update(segment_tree *tree, ll left, ll right, ll row, ll col, ll x) { if(tree == nullptr) return; if(left == right) { tree -> update(col, x); return; } ll mid = left + (right - left) / 2; if(row <= mid) { update(tree -> l, left, mid, row, col, x); } else { update(tree -> r, mid + 1, right, row, col, x); } merge(tree, col); } ll query(segment_tree *tree, ll left, ll right, ll qleft_row, ll qright_row, ll qleft_col, ll qright_col) { if(tree == nullptr) return 0LL; if(qright_row < left || right < qleft_row) return 0LL; if(qleft_row <= left && right <= qright_row) return tree -> query(qleft_col, qright_col); ll mid = left + (right - left) / 2; ll Lnode = query(tree -> l, left, mid, qleft_row, qright_row, qleft_col, qright_col); ll Rnode = query(tree -> r, mid + 1, right, qleft_row, qright_row, qleft_col, qright_col); return gcd2(Lnode, Rnode); } void update(ll row, ll col, ll x) { update(root, 0, n - 1, row, col, x); } ll query(ll qleft_row, ll qright_row, ll qleft_col, ll qright_col) { return query(root, 0, n - 1, qleft_row, qright_row, qleft_col, qright_col); } }; segment_tree_2d s; void init(int R, int C) { n = R; m = C; } void update(int i, int j, long long k) { s.update(i,j,k); } ll calculate(int i1, int j1, int i2, int j2) { ll result = s.query(i1, i2, j1, j2); return result; } /** int main() { ll r,c,n; cin >> r >> c >> n; init(r,c); for(int i = 0; i < n; i++) { ll type; cin >> type; if(type == 1) { ll x,y,w; cin >> x >> y >> w; update(x,y,w); } else { ll i1,j1,i2,j2; cin >> i1 >> j1 >> i2 >> j2; cout << calculate(i1, j1, i2, j2) << endl; } } return 0; } */
#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...