| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1113070 |
2024-11-15T16:04:24 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"
template<int D, typename element, ll N>
struct segtree {
template<int d> using sdim = segtree<d, element, N>;
#define mid (nl + (nr - nl) / 2) // IMP: undef in the end
#define templatic template<class... T>
struct node {
int c[2];
sdim<D - 1> val;
node() { c[0] = c[1] = 0; }
int& operator[](int i) { return c[i]; };
};
vector<node> t;
static constexpr int LIM = (D == 1) * 64; // 64 or 128
vector<pair<ll, element>> cache;
segtree() : t(1) {}
int add_node() {
t.push_back(node());
return (int)t.size() - 1;
}
int go(int n, int d) {
if (!t[n][d]) {
int x = add_node();
t[n][d] = x;
}
return t[n][d];
}
templatic element get(ll i, T... nxt) {
if (t.size() == 1) {
element res;
for (auto& x : cache)
if (x.first == i) res = x.second;
return res;
}
int n = 0; ll l = 0, r = N, m;
do {
m = l + (r - l) / 2;
if (i < m) n = t[n][0], r = m;
else n = t[n][1], l = m;
} while (n && l + 1 < r);
if (!n) return element();
return t[n].val.get(nxt...);
}
templatic element update(element x, ll i, T... nxt) {
if (t.size() == 1) {
bool found = false;
for (auto& v : cache)
if (v.first == i) v.second = x, found = true;
if (!found) cache.emplace_back(i, x);
if (cache.size() < LIM) return x;
for (auto& v : cache)
upd(v.second, 0, 0, N, v.first);
return cache.clear(), x;
}
return upd(x, 0, 0, N, i, nxt...);
}
templatic element upd(element x, ll n, ll nl, ll nr, ll i, T... nxt) {
if (nl + 1 == nr) return t[n].val.update(x, nxt...) , x;
int d = i >= mid;
(i < mid ? nr : nl) = mid;
element lx = upd(x, go(n, d), nl, nr, i, nxt...), rx;
if (t[n][!d]) rx = t[t[n][!d]].val.get(nxt...);
return t[n].val.update(lx * rx, nxt...) , lx * rx;
}
templatic element query(ll l, ll r, T... nxt) {
if (t.size() == 1) {
element res;
for (auto& x : cache)
if (l <= x.first && x.first < r)
res = res * x.second;
return res;
}
return que(0, 0, N, l, r, nxt...);
}
templatic element que(ll n, ll nl, ll nr, ll l, ll r, T... nxt) {
if (nr <= l || r <= nl) return element();
if (l <= nl && nr <= r) return t[n].val.query(nxt...);
return (t[n][0] ? que(t[n][0], nl, mid, l, r, nxt...) : element()) *
(t[n][1] ? que(t[n][1], mid, nr, l, r, nxt...) : element());
}
};
template<typename element, ll N>
struct segtree<0, element, N> {
element val;
segtree() {}
element get() { return val; }
element query() { return val; }
element update(element x) {
return val = x;
}
};
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));
}
};
segtree<2, ele, 1000000005> T;
void init(int R, int C) {
// nothing...
}
void update(int p, int q, ll k) {
T.update(ele(k), p, q);
}
ll calculate(int p, int q, int u, int v) {
return T.query(p, u + 1, q, v + 1).x;
}
Compilation message
game.cpp: In instantiation of 'element segtree<D, element, N>::upd(element, ll, ll, ll, ll, T ...) [with T = {}; int D = 2; element = ele; long long int N = 1000000005; ll = long long int]':
game.cpp:62:8: required from 'element segtree<D, element, N>::update(element, ll, T ...) [with T = {int}; int D = 2; element = ele; long long int N = 1000000005; ll = long long int]'
game.cpp:122:23: required from here
game.cpp:68:43: error: no matching function for call to 'segtree<1, ele, 1000000005>::update(ele&)'
68 | if (nl + 1 == nr) return t[n].val.update(x, nxt...) , x;
| ~~~~~~~~~~~~~~~^~~~~~~~~~~
game.cpp:54:20: note: candidate: 'template<class ... T> element segtree<D, element, N>::update(element, ll, T ...) [with T = {T ...}; int D = 1; element = ele; long long int N = 1000000005]'
54 | templatic element update(element x, ll i, T... nxt) {
| ^~~~~~
game.cpp:54:20: note: template argument deduction/substitution failed:
game.cpp:68:43: note: candidate expects at least 2 arguments, 1 provided
68 | if (nl + 1 == nr) return t[n].val.update(x, nxt...) , x;
| ~~~~~~~~~~~~~~~^~~~~~~~~~~
game.cpp:72:41: error: no matching function for call to 'segtree<1, ele, 1000000005>::get()'
72 | if (t[n][!d]) rx = t[t[n][!d]].val.get(nxt...);
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~
game.cpp:38:20: note: candidate: 'template<class ... T> element segtree<D, element, N>::get(ll, T ...) [with T = {T ...}; int D = 1; element = ele; long long int N = 1000000005]'
38 | templatic element get(ll i, T... nxt) {
| ^~~
game.cpp:38:20: note: template argument deduction/substitution failed:
game.cpp:72:41: note: candidate expects at least 1 argument, 0 provided
72 | if (t[n][!d]) rx = t[t[n][!d]].val.get(nxt...);
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~
game.cpp:73:25: error: no matching function for call to 'segtree<1, ele, 1000000005>::update(ele)'
73 | return t[n].val.update(lx * rx, nxt...) , lx * rx;
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
game.cpp:54:20: note: candidate: 'template<class ... T> element segtree<D, element, N>::update(element, ll, T ...) [with T = {T ...}; int D = 1; element = ele; long long int N = 1000000005]'
54 | templatic element update(element x, ll i, T... nxt) {
| ^~~~~~
game.cpp:54:20: note: template argument deduction/substitution failed:
game.cpp:73:25: note: candidate expects at least 2 arguments, 1 provided
73 | return t[n].val.update(lx * rx, nxt...) , lx * rx;
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
