제출 #855464

#제출 시각아이디문제언어결과실행 시간메모리
855464SanguineChameleon게임 (IOI13_game)C++17
0 / 100
1 ms348 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; struct node_y { map<int, long long> vals; }; node_y* update_y(node_y *u, int y, long long val) { if (!u) { u = new node_y(); } u->vals[y] = val; return u; } long long get_y(node_y *u, int ly, int ry) { if (!u) { return 0LL; } long long res = 0; for (auto [y, val]: u->vals) { if (ly <= y && y <= ry) { res = __gcd(res, val); } } return res; } struct node_x { node_y *root_y; node_x *lch; node_x *rch; node_x(): root_y(nullptr), lch(nullptr), rch(nullptr) {}; }; node_x* update_x(node_x *u, int lt, int rt, int x, int y, long long val) { if (!u) { u = new node_x(); } u->root_y = update_y(u->root_y, y, val); if (lt == rt) { return u; } int mt = (lt + rt) >> 1; if (x <= mt) { u->lch = update_x(u->lch, lt, mt, x, y, val); } else { u->rch = update_x(u->rch, mt + 1, rt, x, y, val); } return u; }; long long get_x(node_x *u, int lt, int rt, int lx, int rx, int ly, int ry) { if (!u) { return 0LL; } if (lt == lx && rt == rx) { return get_y(u->root_y, ly, ry); } int mt = (lt + rt) >> 1; if (rx <= mt) { return get_x(u->lch, lt, mt, lx, rx, ly, ry); } else if (lx >= mt + 1) { return get_x(u->rch, mt + 1, rt, lx, rx, ly, ry); } else { return __gcd(get_x(u->lch, lt, mt, lx, mt, ly, ry), get_x(u->rch, mt + 1, rt, mt + 1, rx, ly, ry)); } } int n, m; node_x *root_x = nullptr; void init(int _n, int _m) { n = _n; m = _m; } void update(int x, int y, long long val) { x++; y++; root_x = update_x(root_x, 1, n, x, y, val); } long long calculate(int lx, int ly, int rx, int ry) { lx++; ly++; rx++; ry++; return get_x(root_x, 1, n, lx, rx, ly, ry); }
#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...