#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>
#ifndef EVAL
#include <iostream>
#endif
#include "wombats.h"
#define entire(a) std::begin((a)), std::end((a))
const int64_t INF = 2'000'000'000'000;
struct Matrix {
int64_t a1 = 0, b1 = INF, a2 = INF, b2 = 0;
Matrix operator*(const Matrix &rhs) const {
return {
.a1 = std::min(a1 + rhs.a1, b1 + rhs.a2),
.a2 = std::min(b2 + rhs.a2, a2 + rhs.a1),
.b1 = std::min(a1 + rhs.b1, b1 + rhs.b2),
.b2 = std::min(b2 + rhs.b2, a2 + rhs.b1),
};
}
};
template <typename T>
struct SegmentTree {
std::vector<T> values;
int offset;
explicit SegmentTree(int sz) : values(2 * sz), offset(sz) {}
void update(int i, T value) {
i += offset;
values[i] = value;
propagate(i);
}
void propagate(int i) {
while (i /= 2) values[i] = values[2 * i] * values[2 * i + 1];
}
T query(int l, int r) {
l += offset;
r += offset;
T left, right;
while (l < r) {
if (l & 1) left = left * values[l++];
if (r & 1) right = values[--r] * right;
}
return left * right;
}
};
std::vector<std::vector<int>> h, v;
int r, c;
SegmentTree st;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
int o = 1;
while (o < 2 * C) o *= 2;
st = SegmentTree<Matrix>(o);
for (int i = 0; i < R; i++) {
st.update(2 * i, {
.a1 = 0,
.a2 = H[i][0],
.b1 = H[i][0],
.b2 = 0,
});
if (i + 1 < R) {
st.update(2 * i + 1, {
.a1 = V[i][0],
.a2 = INF,
.b1 = INF,
.b2 = V[i][1],
});
}
}
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
st.update(2 * P, {
.a1 = 0,
.a2 = h[P][0],
.b1 = h[P][0],
.b2 = 0,
});
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
st.update(2 * P + 1, {
.a1 = v[P][0],
.a2 = INF,
.b1 = INF,
.b2 = v[P][1],
});
}
int escape(int V1, int V2) {
auto res = st.query(0, 2 * r);
if (V1 == 0 && V2 == 0)
return res.a1;
else if (V1 == 0 && V2 == 1)
return res.b1;
else if (V1 == 1 && V2 == 0)
return res.a2;
else if (V1 == 1 && V2 == 1)
return res.b2;
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
wombats.cpp: In member function 'Matrix Matrix::operator*(const Matrix&) const':
wombats.cpp:25:9: error: designator order for field 'Matrix::b1' does not match declaration order in 'Matrix'
25 | };
| ^
wombats.cpp: At global scope:
wombats.cpp:64:13: error: class template argument deduction failed:
64 | SegmentTree st;
| ^~
wombats.cpp:64:13: error: no matching function for call to 'SegmentTree()'
wombats.cpp:34:14: note: candidate: 'template<class T> SegmentTree(int)-> SegmentTree<T>'
34 | explicit SegmentTree(int sz) : values(2 * sz), offset(sz) {}
| ^~~~~~~~~~~
wombats.cpp:34:14: note: template argument deduction/substitution failed:
wombats.cpp:64:13: note: candidate expects 1 argument, 0 provided
64 | SegmentTree st;
| ^~
wombats.cpp:30:8: note: candidate: 'template<class T> SegmentTree(SegmentTree<T>)-> SegmentTree<T>'
30 | struct SegmentTree {
| ^~~~~~~~~~~
wombats.cpp:30:8: note: template argument deduction/substitution failed:
wombats.cpp:64:13: note: candidate expects 1 argument, 0 provided
64 | SegmentTree st;
| ^~
