제출 #489111

#제출 시각아이디문제언어결과실행 시간메모리
489111CYMario게임 (IOI13_game)C++17
100 / 100
6851 ms73220 KiB
#include <stdio.h> #include <stdlib.h> #include <time.h> typedef long long ll; const int N = 300010; //interaction header #include "game.h" ll rd() { ll k = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { k = (k << 1) + (k << 3) + (c ^ 48); c = getchar(); } return f > 0 ? k : -k; } void wr(ll x) { if (x < 0) putchar('-'), x = -x; if (x > 9) wr(x / 10); putchar(x % 10 + '0'); } ll gcd(ll a, ll b) { if (a < 0) a = -a; if (b < 0) b = -a; if (a == 0) return b; if (b == 0) return a; int r = 0; while (!((a & 1) || (b & 1))) a >>= 1, b >>= 1, r++; ll ret = 0; while (1) { while (!(a & 1)) a >>= 1; while (!(b & 1)) b >>= 1; if (a > b) a = a - b; else b = b - a; if (0 == a) { ret = b << r; break; } if (0 == b) { ret = a << r; break; } } return ret; } struct node { node *l, *r; int pos, key, mn, mx; ll val, g; node(int position, ll value) { l = r = nullptr; mn = mx = pos = position; key = rand(); val = g = value; } void pull() { g = val; if (l) g = gcd(g, l->g); if (r) g = gcd(g, r->g); mn = (l ? l->mn : pos); mx = (r ? r->mx : pos); } }; // memory O(n) struct treap { node *root; treap() { root = nullptr; } void split(node *t, int pos, node *&l, node *&r) { if (t == nullptr) { l = r = nullptr; return; } if (t->pos < pos) { split(t->r, pos, l, r); t->r = l; l = t; } else { split(t->l, pos, l, r); t->l = r; r = t; } t->pull(); } node *merge(node *l, node *r) { if (!l || !r) return l ? l : r; if (l->key < r->key) { l->r = merge(l->r, r); l->pull(); return l; } r->l = merge(l, r->l); r->pull(); return r; } bool find(int pos) { node *t = root; while (t) { if (t->pos == pos) return true; if (t->pos > pos) t = t->l; else t = t->r; } return false; } void upd(node *t, int pos, ll val) { if (t->pos == pos) { t->val = val; t->pull(); return; } if (t->pos > pos) upd(t->l, pos, val); else upd(t->r, pos, val); t->pull(); } void insert(int pos, ll val) { // set a_pos = val if (find(pos)) upd(root, pos, val); else { node *l, *r; split(root, pos, l, r); root = merge(merge(l, new node(pos, val)), r); } } ll query(node *t, int st, int en) { if (t->mx < st || en < t->mn) return 0; if (st <= t->mn && t->mx <= en) return t->g; ll ans = (st <= t->pos && t->pos <= en ? t->val : 0); if (t->l) ans = gcd(ans, query(t->l, st, en)); if (t->r) ans = gcd(ans, query(t->r, st, en)); return ans; } ll query(int l, int r) { // gcd of a_i such that l <= i <= r if (!root) return 0; return query(root, l, r); } void print(node *t) { if (!t) return; print(t->l); wr(t->val), putchar('\n'); print(t->r); } }; // Dynamic 2D Query Tree From Shahjalal Shohag // total memory along with treap = nlogn struct ST { ST *l, *r; treap t; int b, e; ST() { l = r = nullptr; } ST(int st, int en) { l = r = nullptr; b = st, e = en; } void fix(int pos) { ll val = 0; if (l) val = gcd(val, l->t.query(pos, pos)); if (r) val = gcd(val, r->t.query(pos, pos)); t.insert(pos, val); } void upd(int x, int y, ll val) { // set a[x][y] = val if (e < x || x < b) return; if (b == e) { t.insert(y, val); return; } if (b != e) { if (x <= (b + e) / 2) { if (!l) l = new ST(b, (b + e) / 2); l->upd(x, y, val); } else { if (!r) r = new ST((b + e) / 2 + 1, e); r->upd(x, y, val); } } fix(y); } // gcd of a[x][y] such that i <= x <= j && st <= y <= en ll query(int i, int j, int st, int en) { if (e < i || j < b) return 0; if (i <= b && e <= j) return t.query(st, en); ll ans = 0; if (l) ans = gcd(ans, l->query(i, j, st, en)); if (r) ans = gcd(ans, r->query(i, j, st, en)); return ans; } }; ST t; void init(int R, int C) { srand(time(NULL)); t = ST(0, R - 1); } void update(int P, int Q, long long K) { t.upd(P, Q, K); } long long calculate(int P, int Q, int U, int V) { return t.query(P, U, Q, V); } void test_interaction() { int n = rd(), m = rd(); init(n, m); int q = rd(); while(q--) { int op = rd(); //op 1 : update single point if (op == 1) { int x = rd(), y = rd(); ll w = rd(); update(x, y, w); } //op 2 : 2D gcd query else { int xl = rd(), yl = rd(), xr = rd(), yr = rd(); wr(calculate(xl, xr, yl, yr)), putchar('\n'); } } }
#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...