| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1087555 |
2024-09-12T23:32:54 Z |
Noam527 |
Game (IOI13_game) |
C++17 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ldb;
const int md = (int)1e9 + 7;
const ll inf = 2e18;
const int OO = 1;
using namespace std;
#include "game.h"
/*
* note the "using T = int". this is the range of indicies we allow.
* note the static constant LIM. used for efficiency of both time and memory. practice shows that 64 or 128 are the best.
* ASSUMES COMMUTATIVITY - to fix, make `query` call the recursive version immediately (i.e no use of `big`).
*/
template<typename element>
struct segtree {
using T = int;
struct node {
element val;
int c[2];
node(element v = element()) : c({ 0,0 }), val(v) {}
int& operator [](int i) {
return c[i];
}
};
T L, R;
vector<node> t;
static const int LIM = 64;
vector<pair<T, element>> last;
bool big;
T cache_i;
element cache_v;
segtree() {}
segtree(T LL, T RR) : L(LL), R(RR) {
t.push_back(node()); // dummy
t.push_back(node()); // root
big = 0;
cache_i = L;
cache_v = element();
}
int add_node() {
t.push_back(node());
return (int)t.size() - 1;
}
int go(int v, int dir) {
if (!t[v][dir]) {
int x = add_node(); // prevents bug from reallocation
t[v][dir] = x;
}
return t[v][dir];
}
void fix(int v) {
t[v].val = t[t[v].l].val * t[t[v].r].val;
}
void update(T pos, element val) {
cache_i = pos, cache_v = val;
if (big) {
update(pos, val, 1, L, R);
return;
}
bool found = false;
for (auto& i : last) {
if (i.first == pos) {
i.second = val;
found = true;
break;
}
}
if (!found) last.emplace_back(pos, val);
if (last.size() < LIM) return;
for (const auto& i : last)
update(i.first, i.second, 1, L, R);
last.clear();
big = 1;
}
void update(T pos, element val, int node, T nl, T nr) {
if (nl == nr) {
t[node].val = val;
return;
}
T mid = (nl + nr) / 2;
if (pos <= mid) update(pos, val, go(node, 0), nl, mid);
else update(pos, val, go(node, 1), mid + 1, nr);
fix(node);
}
// implement only if you need quick access to a single index (instead of range)
element get(T i) {
if (i == cache_i) return cache_v;
if (!big) {
for (const auto& j : last)
if (j.first == i) return j.second;
return element();
}
int node = 1;
T l = L, r = R;
while (l < r) {
T mid = (l + r) / 2;
if (i <= mid) {
if (!t[node][0]) return element();
node = t[node][0];
r = mid;
}
else {
if (!t[node][1]) return element();
node = t[node][1];
l = mid + 1;
}
}
return t[node].val;
}
element query(T l, T r) {
if (l > r) return element();
if (!big) {
element res;
for (const auto& i : last)
if (l <= i.first && i.first <= r)
res = res * i.second;
return res;
}
return query(l, r, 1, L, R);
}
element query(T l, T r, int node, T nl, T nr) {
if (r < nl || nr < l) return element();
if (l <= nl && nr <= r) return t[node].val;
T mid = (nl + nr) / 2;
if (r <= mid || !t[node][1]) {
if (!t[node][0]) return element();
return query(l, r, t[node][0], nl, mid);
}
if (mid < l || !t[node][0])
return query(l, r, t[node][1], mid + 1, nr);
return query(l, r, t[node][0], nl, mid) * query(l, r, t[node][1], mid + 1, nr);
}
};
template<typename element>
struct segtree2D {
using T = int;
struct node {
segtree<element> val;
int l, r;
node() {}
node(T L, T R) {
l = -1, r = -1;
val = segtree<element>(L, R);
}
};
T L0, R0, L1, R1;
vector<node> t;
segtree2D() {}
segtree2D(T l0, T r0, T l1, T r1) : L0(l0), R0(r0), L1(l1), R1(r1) {
t.push_back(node(L1, R1));
}
int add_node() {
t.push_back(node(L1, R1));
return (int)t.size() - 1;
}
int go_left(int v) {
if (t[v].l == -1) {
int x = add_node(); // prevents bug from reallocation
t[v].l = x;
}
return t[v].l;
}
int go_right(int v) {
if (t[v].r == -1) {
int x = add_node(); // prevents bug from reallocation
t[v].r = x;
}
return t[v].r;
}
void fix(int node, T pos1) {
// assumes node has at least 1 child
element val;
if (t[node].l == -1) val = t[t[node].r].val.get(pos1);
else if (t[node].r == -1) val = t[t[node].l].val.get(pos1);
else val = t[t[node].l].val.get(pos1) * t[t[node].r].val.get(pos1);
t[node].val.update(pos1, val);
}
void update(T pos0, T pos1, element val) {
update(pos0, pos1, val, 0, L0, R0);
}
void update(T pos0, T pos1, element val, int node, T nl, T nr) {
if (nl == nr) {
t[node].val.update(pos1, val);
return;
}
T mid = (nl + nr) / 2;
if (pos0 <= mid) update(pos0, pos1, val, go_left(node), nl, mid);
else update(pos0, pos1, val, go_right(node), mid + 1, nr);
fix(node, pos1);
}
element query(T l0, T r0, T l1, T r1) {
if (l0 > r0 || l1 > r1) return element();
return query(l0, r0, l1, r1, 0, L0, R0);
}
element query(T l0, T r0, T l1, T r1, int node, T nl, T nr) {
if (r0 < nl || nr < l0) return element();
if (l0 <= nl && nr <= r0) {
return t[node].val.query(l1, r1);
}
T mid = (nl + nr) / 2;
if (r0 <= mid || t[node].r == -1) {
if (t[node].l == -1) return element();
return query(l0, r0, l1, r1, t[node].l, nl, mid);
}
if (mid < l0 || t[node].l == -1)
return query(l0, r0, l1, r1, t[node].r, mid + 1, nr);
return query(l0, r0, l1, r1, t[node].l, nl, mid) * query(l0, r0, l1, r1, t[node].r, mid + 1, nr);
}
};
ll gcd(ll x, ll y) {
return !y ? x : gcd(y, x % y);
}
struct ele {
ll x;
ele(ll xx = 0) : x(xx) {}
ele operator * (const ele &a) const {
return ele(gcd(x, a.x));
}
};
segtree2D<ele> T;
void init(int R, int C) {
T = segtree2D<ele>(0, R - 1, 0, C - 1);
}
void update(int p, int q, ll k) {
T.update(p, q, k);
}
ll calculate(int p, int q, int u, int v) {
return T.query(p, u, q, v).x;
}
Compilation message
game.cpp: In instantiation of 'segtree<element>::node::node(element) [with element = ele]':
game.cpp:37:15: required from 'segtree<element>::segtree(segtree<element>::T, segtree<element>::T) [with element = ele; segtree<element>::T = int]'
game.cpp:147:10: required from 'segtree2D<element>::node::node(segtree2D<element>::T, segtree2D<element>::T) [with element = ele; segtree2D<element>::T = int]'
game.cpp:154:15: required from 'segtree2D<element>::segtree2D(segtree2D<element>::T, segtree2D<element>::T, segtree2D<element>::T, segtree2D<element>::T) [with element = ele; segtree2D<element>::T = int]'
game.cpp:230:39: required from here
game.cpp:21:7: warning: 'segtree<ele>::node::c' will be initialized after [-Wreorder]
21 | int c[2];
| ^
game.cpp:20:11: warning: 'ele segtree<ele>::node::val' [-Wreorder]
20 | element val;
| ^~~
game.cpp:22:3: warning: when initialized here [-Wreorder]
22 | node(element v = element()) : c({ 0,0 }), val(v) {}
| ^~~~
game.cpp:22:50: warning: list-initializer for non-class type must not be parenthesized
22 | node(element v = element()) : c({ 0,0 }), val(v) {}
| ^
game.cpp: In instantiation of 'void segtree<element>::fix(int) [with element = ele]':
game.cpp:86:3: required from 'void segtree<element>::update(segtree<element>::T, element, int, segtree<element>::T, segtree<element>::T) [with element = ele; segtree<element>::T = int]'
game.cpp:60:10: required from 'void segtree<element>::update(segtree<element>::T, element) [with element = ele; segtree<element>::T = int]'
game.cpp:187:22: required from 'void segtree2D<element>::update(segtree2D<element>::T, segtree2D<element>::T, element, int, segtree2D<element>::T, segtree2D<element>::T) [with element = ele; segtree2D<element>::T = int]'
game.cpp:183:9: required from 'void segtree2D<element>::update(segtree2D<element>::T, segtree2D<element>::T, element) [with element = ele; segtree2D<element>::T = int]'
game.cpp:234:18: required from here
game.cpp:55:21: error: '__gnu_cxx::__alloc_traits<std::allocator<segtree<ele>::node>, segtree<ele>::node>::value_type' {aka 'struct segtree<ele>::node'} has no member named 'l'
55 | t[v].val = t[t[v].l].val * t[t[v].r].val;
| ~~~~~^
game.cpp:55:37: error: '__gnu_cxx::__alloc_traits<std::allocator<segtree<ele>::node>, segtree<ele>::node>::value_type' {aka 'struct segtree<ele>::node'} has no member named 'r'
55 | t[v].val = t[t[v].l].val * t[t[v].r].val;
| ~~~~~^
