結果

問題 No.2332 Make a Sequence
ユーザー Ricky_pon
提出日時 2023-05-28 15:16:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 166 ms / 2,000 ms
コード長 6,382 bytes
コンパイル時間 2,452 ms
コンパイル使用メモリ 160,936 KB
最終ジャッジ日時 2025-02-13 12:53:09
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:210:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  210 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
main.cpp:212:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  212 |     rep(i, n) scanf("%d", &a[i]);
      |               ~~~~~^~~~~~~~~~~~~
main.cpp:213:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  213 |     rep(i, m) scanf("%d", &b[i]);
      |               ~~~~~^~~~~~~~~~~~~
main.cpp:215:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  215 |     rep(i, m) scanf("%lld", &c[i]);
      |               ~~~~~^~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <ciso646>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define REP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME
#define REP3(i, l, r, s) \
for (int i = int(l), rep3_r = int(r), rep3_s = int(s); i < rep3_r; \
i += rep3_s)
#define REP2(i, l, r) REP3(i, l, r, 1)
#define REP1(i, n) REP2(i, 0, n)
#define rep(...) REP_OVERLOAD(__VA_ARGS__, REP3, REP2, REP1, )(__VA_ARGS__)
#define repin(i, l, r) for (int i = int(l), repin_r = int(r); i <= repin_r; ++i)
#define RREP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME
#define RREP3(i, l, r, s) \
for (int i = int(r) - 1, rrep3_l = int(l), rrep3_s = int(s); i >= rrep3_l; \
i -= rrep3_s)
#define RREP2(i, l, r) RREP3(i, l, r, 1)
#define RREP1(i, n) RREP2(i, 0, n)
#define rrep(...) RREP_OVERLOAD(__VA_ARGS__, RREP3, RREP2, RREP1, )(__VA_ARGS__)
#define rrepin(i, l, r) \
for (int i = int(r), rrepin_l = int(l); i >= rrepin_l; --i)
#define fi first
#define se second
#include <atcoder/string>
#include <algorithm>
#include <cassert>
#include <vector>
namespace rklib {
template <class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
bool chmin_non_negative(T &a, const T &b) {
if (a < 0 || a > b) {
a = b;
return true;
}
return false;
}
template <class T>
T div_floor(T num, T den) {
if (den < 0) num = -num, den = -den;
return num >= 0 ? num / den : (num + 1) / den - 1;
}
template <class T>
T div_ceil(T num, T den) {
if (den < 0) num = -num, den = -den;
return num <= 0 ? num / den : (num - 1) / den + 1;
}
} // namespace rklib
using namespace std;
using namespace rklib;
using lint = long long;
using pii = pair<int, int>;
using pll = pair<lint, lint>;
template <typename T, T inf>
class LiChaoTree {
public:
LiChaoTree() = default;
explicit LiChaoTree(const std::vector<T>& x) : xs(x) {
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
n = (int)xs.size();
sz = 1;
while (sz < n) sz <<= 1;
while ((int)xs.size() < sz) xs.emplace_back(xs.back() + 1);
node.resize(sz * 2, Line(T(0), inf));
}
// ax + b
void add_line(T a, T b) { update(a, b, 0, sz, 1); }
// ax + b (x_l <= x < x_r)
void add_segment(T a, T b, T x_l, T x_r) {
int l = std::lower_bound(xs.begin(), xs.end(), x_l) - xs.begin();
int r = std::lower_bound(xs.begin(), xs.end(), x_r) - xs.begin();
l += sz;
r += sz;
int width = 1, seg_idx_left = sz;
while (l < r) {
if (l & 1) {
int L = (l - seg_idx_left) * width;
int R = L + width;
update(a, b, L, R, l);
l++;
}
if (r & 1) {
r--;
int L = (r - seg_idx_left) * width;
int R = L + width;
update(a, b, L, R, r);
}
l >>= 1;
r >>= 1;
width <<= 1;
seg_idx_left >>= 1;
}
}
// min_{i} (a_i * x + b)
T get_min(T x) {
int pos = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();
assert(0 <= pos and pos < sz);
pos += sz;
T ret = node[pos].eval(x);
while (pos > 1) {
pos >>= 1;
ret = std::min(ret, node[pos].eval(x));
}
return ret;
}
private:
struct Line {
T a, b;
Line(T a, T b) : a(a), b(b) {}
inline T eval(T x) const { return (a * x + b); }
};
std::vector<T> xs;
std::vector<Line> node;
int n, sz;
void update(T a, T b, int l, int r, int pos) {
Line new_line(a, b);
while (1) {
bool is_over_l = (new_line.eval(xs[l]) >= node[pos].eval(xs[l]));
bool is_over_r =
(new_line.eval(xs[r - 1]) >= node[pos].eval(xs[r - 1]));
if (is_over_l == is_over_r) {
if (!is_over_l) node[pos] = new_line;
break;
}
int mid = (l + r) >> 1;
bool is_over_mid =
(new_line.eval(xs[mid]) >= node[pos].eval(xs[mid]));
if (!is_over_l and is_over_r) {
if (is_over_mid) {
r = mid;
pos = (pos << 1);
} else {
std::swap(new_line, node[pos]);
l = mid;
pos = (pos << 1) | 1;
}
} else {
if (is_over_mid) {
l = mid;
pos = (pos << 1) | 1;
} else {
std::swap(new_line, node[pos]);
r = mid;
pos = (pos << 1);
}
}
}
}
};
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n), b(m);
rep(i, n) scanf("%d", &a[i]);
rep(i, m) scanf("%d", &b[i]);
vector<lint> c(m);
rep(i, m) scanf("%lld", &c[i]);
vector<int> ab = a;
ab.push_back(-1);
for (auto x : b) ab.push_back(x);
auto z = atcoder::z_algorithm(ab);
z.erase(z.begin(), z.begin() + n + 1);
vector<lint> xs(m + 10);
iota(xs.begin(), xs.end(), 0);
LiChaoTree<lint, LLONG_MAX> lct(xs);
lct.add_segment(0, 0, 0, 1);
rep(x, m) {
auto val = lct.get_min(x);
if (val == LLONG_MAX) continue;
if (z[x] >= 1) {
lct.add_segment(c[x], val - c[x] * x, x + 1, x + z[x] + 1);
}
}
auto ans = lct.get_min(m);
printf("%lld\n", ans == LLONG_MAX ? -1 : ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0