| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 330042 |
2020-11-23T14:05:42 Z |
2qbingxuan |
Game (IOI13_game) |
C++14 |
|
154 ms |
256004 KB |
#include <bits/stdc++.h>
#ifndef local
#include "game.h"
#endif // local
using namespace std;
using ll = long long;
const int N = 22000, LG = 30;
inline ll gcd(ll a, ll b) {
int s = __builtin_ctz(a | b);
while(a && b) {
a >>= __builtin_ctz(a);
b >>= __builtin_ctz(b);
if(a > b) a -= b;
else b -= a;
}
return (a | b) << s;
}
int R, C;
struct Segtree1d {
// 1d, dynamic
struct node {
ll ans;
node *l, *r;
node() : ans(0), l(nullptr), r(nullptr) {}
void pull() {
ans = gcd( l ? l->ans : 0, r ? r->ans : 0);
}
} *root;
static node mem[N * LG * LG], *ptr;
void modify(int pos, ll v, node *&cur, int l, int r) {
if(!cur) cur = new node();
if(l+1 == r) {
cur->ans = v;
return;
}
int m = l+(r-l)/2;
if(pos < m)
modify(pos, v, cur->l, l, m);
else
modify(pos, v, cur->r, m, r);
cur->pull();
}
ll query(int ql, int qr, node *cur, int l, int r) {
if(l >= qr || r <= ql || !cur) return 0;
if(ql <= l && r <= qr) return cur->ans;
int m = l+(r-l)/2;
return gcd(query(ql, qr, cur->l, l, m), query(ql, qr, cur->r, m, r));
}
Segtree1d() : root(nullptr) {}
void modify(int pos, ll v) {
modify(pos, v, root, 0, C);
}
ll query(int l, int r) {
return query(l, r, root, 0, C);
}
};
Segtree1d::node Segtree1d::mem[N * LG * LG], *Segtree1d::ptr = Segtree1d::mem;
/*
struct Splay {
struct node {
int key;
ll val, ans;
node *ch[2], *pa;
node(int k, ll v) : key(k), val(v), ans(v), ch{}, pa(0) {}
node() : key(-1), val(0), ans(0), ch{}, pa(0) {}
void pull() {
ans = gcd(val, gcd(ch[0] ? ch[0]->ans : 0, ch[1] ? ch[1]->ans : 0));
}
friend bool dir(node *x) { return x->pa && x->pa->ch[1] == x; }
} *root;
void rot(node *x) {
bool d = dir(x);
node *y = x->pa, *z = (y ? y->pa : nullptr);
x->pa = z;
if(z) z->ch[dir(y)] = x;
if(x->ch[!d]) x->ch[!d]->pa = y;
y->ch[d] = x->ch[!d];
y->pa = x;
x->ch[!d] = y;
y->pull(), x->pull();
}
void splay(node *x) {
while(node *y = x->pa) {
if(y->pa)
rot(dir(x) != dir(y) ? x : y);
rot(x);
}
}
void split(int k, node *x, node *&a, node *&b) {
// a: key < k, b: key >= k
node *y = nullptr, *last = nullptr;
while(x) {
last = x;
if(x->key < k) {
x = x->ch[1];
} else {
y = x;
x = x->ch[0];
}
}
if(last) splay(last);
if(!y) return a = last, b = nullptr, void();
splay(y);
a = y->ch[0];
if(a) a->pa = nullptr;
y->ch[0] = nullptr;
b = y;
b->pull();
}
node *join(node *a, node *b) {
if(!a || !b) return a ? a : b;
while(a->ch[1]) a = a->ch[1];
while(b->ch[0]) b = b->ch[0];
splay(a), splay(b);
b->ch[0] = a;
a->pa = b;
b->pull();
return b;
}
static node mem[N * LG], *ptr;
void modify(int p, ll v) {
node *a, *b, *c;
split(p, root, a, b);
split(p+1, b, b, c);
if(b == nullptr)
b = new (ptr++) node(p, v);
else
b->val = b->ans = v;
root = join(a, join(b, c));
}
ll query(int l, int r) {
node *a, *b, *c;
split(l, root, a, b);
split(r, b, b, c);
ll res = b ? b->ans : 0;
root = join(a, join(b, c));
return res;
}
Splay() : root(nullptr) {}
};
Splay::node Splay::mem[N * LG], *Splay::ptr = Splay::mem;
*/
struct Segtree2d {
struct node {
Segtree1d st;
node *l, *r;
node() : l(nullptr), r(nullptr) {}
// Complexity of pull would TLE
// Notice that only posy would change
void pull(int y) {
st.modify(y, gcd(l ? l->st.query(y, y+1) : 0, r ? r->st.query(y, y+1) : 0));
}
} *root;
static node mem[N * LG], *ptr;
void modify(int posx, int posy, ll v, node *&cur, int l, int r) {
if(!cur) cur = new node();
if(l+1 == r) {
cur->st.modify(posy, v);
return;
}
int m = l+(r-l)/2;
if(posx < m)
modify(posx, posy, v, cur->l, l, m);
else
modify(posx, posy, v, cur->r, m, r);
cur->pull(posy);
}
ll query(int lx, int rx, int ly, int ry, node *cur, int l, int r) {
if(r <= lx || l >= rx || !cur) return 0;
if(lx <= l && r <= rx) return cur->st.query(ly, ry);
int m = l+(r-l)/2;
return gcd(query(lx, rx, ly, ry, cur->l, l, m), query(lx, rx, ly, ry, cur->r, m, r));
}
Segtree2d() : root(nullptr) {}
void modify(int posx, int posy, ll v) {
modify(posx, posy, v, root, 0, R);
}
ll query(int lx, int rx, int ly, int ry) {
return query(lx, rx, ly, ry, root, 0, R);
}
} sgt;
Segtree2d::node Segtree2d::mem[N * LG], *Segtree2d::ptr = Segtree2d::mem;
void init(int r, int c) {
R = r, C = c;
}
void update(int x, int y, ll k) {
sgt.modify(x, y, k);
}
ll calculate(int lx, int ly, int rx, int ry) {
if(lx > rx) swap(lx, rx);
if(ly > ry) swap(ly, ry);
return sgt.query(lx, rx+1, ly, ry+1);
}
#ifdef local
signed main() {
;
}
#endif // local
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
139 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
143 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
140 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
154 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
143 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
