QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#120623 | #1154. Wombats | Qwerty1232# | Compile Error | / | / | C++17 | 3.9kb | 2023-07-07 01:35:23 | 2024-05-26 02:57:05 |
Judging History
你现在查看的是最新测评结果
- [2024-05-26 02:57:05]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-07-07 01:35:23]
- 提交
answer
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "wombats.h"
#include <bits/stdc++.h>
constexpr int inf = 1e9 + 1;
int n, m;
struct Cum {
std::vector<int> L;
std::vector<std::vector<int>> data;
std::vector<std::vector<int>> v, h;
int len;
Cum() {
len = 0;
}
Cum(std::vector<int> v, std::vector<int> h) {
assert(v.size() == m);
assert(h.size() == m - 1);
len = 1;
L = v;
this->v.push_back(v);
this->h.push_back(h);
return;
std::vector<int> ph(m);
std::partial_sum(h.begin(), h.end(), ph.begin() + 1);
data.assign(m, std::vector<int>(m));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
data[i][j] = abs(ph[i] - ph[j]);
}
}
}
};
Cum fuck(Cum a) {
if (a.len == -1) {
return a;
}
int l = a.len;
Cum res;
res.len = -1;
res.data.resize(m);
res.L = a.L;
for (int i = 0; i < m; i++) {
std::vector<int> dp(m, inf);
dp[i] = 0;
auto shit = [&](auto& h) {
for (int j = 1; j < m; j++) {
dp[j] = std::min(dp[j], dp[j - 1] + h[j - 1]);
}
for (int j = m - 2; j >= 0; j--) {
dp[j] = std::min(dp[j], dp[j + 1] + h[j]);
}
};
shit(a.h[0]);
for (int j = 1; j < l; j++) {
for (int t = 0; t < m; t++) {
dp[t] += a.v[j][t];
}
shit(a.h[j]);
}
res.data[i] = dp;
}
return res;
}
Cum merge(Cum a, Cum b) {
if (!a.len || !b.len) {
return a.len ? a : b;
}
// a = fuck(a);
// b = fuck(b);
if (a.len == -1 || b.len == -1) {
if (a.len != -1) {
a = fuck(a);
}
if (b.len != -1) {
b = fuck(b);
}
} else {
a.len += b.len;
a.v.insert(a.v.end(), b.v.begin(), b.v.end());
a.h.insert(a.h.end(), b.h.begin(), b.h.end());
if (a.len > 30) {
a = fuck(a);
}
return a;
}
Cum res;
res.len = -1;
res.L = a.L;
res.data.assign(m, std::vector<int>(m, inf));
const int const_m = m;
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
int val = a.data[i][j] + b.L[j];
#pragma GCC ivdep
for (int t = 0; t < const_m; t++) {
res.data[i][t] = std::min(res.data[i][t], val + b.data[j][t]);
}
}
}
return res;
}
std::vector<std::vector<int>> h, v;
int size;
std::vector<Cum> data;
void build() {
for (size = 1; size < n; size *= 2)
;
data.resize(2 * size);
for (int i = 0; i < n; i++) {
data[size + i] = Cum(v[i], h[i]);
}
for (int i = size - 1; i > 0; i--) {
data[i] = merge(data[2 * i], data[2 * i + 1]);
}
}
void update(int i) {
data[i + size] = Cum(v[i], h[i]);
i += size;
for (i >>= 1; i > 0; i >>= 1) {
data[i] = merge(data[2 * i], data[2 * i + 1]);
}
}
void init(int r, int c, int H[5000][200], int V[5000][200]) {
n = r;
m = c;
h.assign(n, std::vector<int>(m - 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
h[i][j] = H[i][j];
}
}
v.assign(n, std::vector<int>(m));
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
v[i + 1][j] = V[i][j];
}
}
build();
}
void changeH(int p, int q, int w) {
h[p][q] = w;
update(p);
}
void changeV(int p, int q, int w) {
v[p + 1][q] = w;
update(p + 1);
}
int escape(int v1, int v2) {
if (data[1].len != -1) {
data[1] = fuck(data[1]);
}
int res = data[1].data[v1][v2];
return res;
// return 42;
}
详细
In file included from /usr/include/c++/13/string:43, from /usr/include/c++/13/bitset:52, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52, from answer.code:5: /usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’: /usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch 184 | ~allocator() _GLIBCXX_NOTHROW { } | ^ In file included from /usr/include/c++/13/vector:66, from /usr/include/c++/13/functional:64, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53: /usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here 133 | struct _Vector_impl | ^~~~~~~~~~~~