Submission #489173

#TimeUsernameProblemLanguageResultExecution timeMemory
489173CYMarioGame (IOI13_game)C++17
100 / 100
2087 ms39816 KiB
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <utility> #include "game.h" typedef long long ll; const int N = 300010; using namespace std; typedef pair<int, int> ii; //from errorgorn 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'); } inline long long func(long long X, long long Y) { long long tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; //return X + Y; } /* int __builtin_clz(int x) { if (!x)return 32; int ret = 0; //if (!(x & 0xFFFFFFFF00000000ll)) ret += 32, x <<= 32; if (!(x & 0xFFFF0000)) ret += 16, x <<= 16; if (!(x & 0xFF000000)) ret += 8, x <<= 8; if (!(x & 0xF0000000)) ret += 4, x <<= 4; if (!(x & 0xC0000000)) ret += 2, x <<= 2; if (!(x & 0x80000000)) ret += 1, x <<= 1; return ret; } */ ii lca(int l, int r, int pos) { // find lca of 2 nodes if (pos < l) { int p = 32 - __builtin_clz(pos ^ l); int lp = (pos >> p) << p; return ii(lp, lp + (1 << p) - 1); } if (r < pos) { int p = 32 - __builtin_clz(r ^ pos); int lp = (l >> p) << p; return ii(lp, lp + (1 << p) - 1); } return ii(pos, 0); } struct node { int s, e, m; long long val = 0; node *l = nullptr, *r = nullptr; node(int _s, int _e) { s = _s, e = _e, m = (s + e) >> 1; } bool inside(int i) { return s <= i && i <= e; } void update(int i, long long j) { if (s == e) val = j; else { if (i <= m) { if (l == nullptr) l = new node(i, i); else if (!l->inside(i)) { node *temp = l; ii child = lca(l->s, l->e, i); l = new node(child.first, child.second); if (temp->e <= l->m) l->l = temp; else l->r = temp; } l->update(i, j); } else { if (r == nullptr) r = new node(i, i); else if (!r->inside(i)) { node *temp = r; ii child = lca(r->s, r->e, i); r = new node(child.first, child.second); if (temp->e <= r->m) r->l = temp; else r->r = temp; } r->update(i, j); } val = func((l == nullptr) ? 0 : l->val, (r == nullptr) ? 0 : r->val); } } long long query(int i, int j) { if (i <= s && e <= j) return val; else if (j <= m) return (l == nullptr) ? 0 : l->query(i, j); else if (m < i) return (r == nullptr) ? 0 : r->query(i, j); else return func((l == nullptr) ? 0 : l->query(i, m), (r == nullptr) ? 0 : r->query(m + 1, j)); } node *clone() { node *res = new node(s, e); res->val = val; res->l = (l == nullptr) ? nullptr : l->clone(); res->r = (r == nullptr) ? nullptr : r->clone(); return res; } }; struct node2d { int s, e, m; node *val = new node(0, (1 << 30) - 1); node2d *l = nullptr, *r = nullptr; node2d(int _s, int _e) { s = _s, e = _e, m = s + e >> 1; } bool inside(int i) { return s <= i && i <= e; } void update(int i, int j, long long k) { if (s == e) val->update(j, k); else { if (i <= m) { if (l == nullptr) l = new node2d(i, i); else if (!l->inside(i)) { node2d *temp = l; ii child = lca(l->s, l->e, i); l = new node2d(child.first, child.second); if (temp->e <= l->m) l->l = temp; else l->r = temp; l->val = temp->val->clone(); } l->update(i, j, k); } else { if (r == nullptr) r = new node2d(i, i); else if (!r->inside(i)) { node2d *temp = r; ii child = lca(r->s, r->e, i); r = new node2d(child.first, child.second); if (temp->e <= r->m) r->l = temp; else r->r = temp; r->val = temp->val->clone(); } r->update(i, j, k); } val->update(j, func((l == nullptr) ? 0 : l->val->query(j, j), (r == nullptr) ? 0 : r->val->query(j, j))); } } long long query(int i, int j, int i2, int j2) { if (i <= s && e <= j) return val->query(i2, j2); else if (j <= m) return (l == nullptr) ? 0 : l->query(i, j, i2, j2); else if (m < i) return (r == nullptr) ? 0 : r->query(i, j, i2, j2); else return func((l == nullptr) ? 0 : l->query(i, m, i2, j2), (r == nullptr) ? 0 : r->query(m + 1, j, i2, j2)); } } *root = new node2d(0, (1 << 30) - 1); void init(int R, int C) { } void update(int P, int Q, long long K) { root->update(P, Q, K); } long long calculate(int P, int Q, int U, int V) { return root->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, yl, xr, yr)), putchar('\n'); } } }

Compilation message (stderr)

game.cpp: In constructor 'node2d::node2d(int, int)':
game.cpp:169:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |         s = _s, e = _e, m = s + e >> 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...