結果
問題 |
No.704 ゴミ拾い Medium
|
ユーザー |
![]() |
提出日時 | 2025-03-21 17:46:02 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 1,500 ms |
コード長 | 2,359 bytes |
コンパイル時間 | 412 ms |
コンパイル使用メモリ | 29,952 KB |
実行使用メモリ | 11,520 KB |
最終ジャッジ日時 | 2025-03-21 17:46:10 |
合計ジャッジ時間 | 7,452 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 44 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:69:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 69 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:71:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 71 | scanf("%d", a + i); | ~~~~~^~~~~~~~~~~~~ main.cpp:73:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 73 | scanf("%d", x + i); | ~~~~~^~~~~~~~~~~~~ main.cpp:75:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 75 | scanf("%d", y + i); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <stdio.h> int n, a[300005], x[300005], y[300005]; long long dp[300005]; namespace segmentTree { int val[400005]; long long k[400005], b[400005]; inline int lson(int x) { return x << 1; } inline int rson(int x) { return x << 1 | 1; } inline long long abs(long long x) { return x < 0 ? -x : x; } inline long long function(long long k, long long b, long long x) { return abs(x - k) + b; } inline long long min(long long x, long long y) { return x < y ? x : y; } void build(int root, int tl, int tr) { k[root] = 1000000000; b[root] = 1e18; if (tl != tr) { int tm = (tl + tr) >> 1; build(lson(root), tl, tm); build(rson(root), tm + 1, tr); } } void update(int newk, long long newb, int root, int tl, int tr) { bool lbetter = function(k[root], b[root], tl) > function(newk, newb, tl); bool rbetter = function(k[root], b[root], tr) > function(newk, newb, tr); if (lbetter && rbetter) { k[root] = newk; b[root] = newb; return; } if (!lbetter && !rbetter) return; int tm = (tl + tr) >> 1; bool mlbetter = function(k[root], b[root], tm) > function(newk, newb, tm); if (lbetter && mlbetter) { k[root] ^= newk ^= k[root] ^= newk; b[root] ^= newb ^= b[root] ^= newb; return update(newk, newb, rson(root), tm + 1, tr); } bool mrbetter = function(k[root], b[root], tm + 1) > function(newk, newb, tm + 1); if (rbetter && mrbetter) { k[root] ^= newk ^= k[root] ^= newk; b[root] ^= newb ^= b[root] ^= newb; return update(newk, newb, lson(root), tl, tm); } if (lbetter) update(newk, newb, lson(root), tl, tm); else update(newk, newb, rson(root), tm + 1, tr); } long long query(int i, int root, int tl, int tr) { if (i < tl || tr < i) return 2e18; long long res = function(k[root], b[root], i); if (tl == tr) return res; int tm = (tl + tr) >> 1; return min(res, i <= tm ? query(i, lson(root), tl, tm) : query(i, rson(root), tm + 1, tr)); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a + i); for (int i = 1; i <= n; ++i) scanf("%d", x + i); for (int i = 1; i <= n; ++i) scanf("%d", y + i); segmentTree::build(1, 0, 100000); for (int i = 1; i <= n; ++i) { segmentTree::update(x[i], dp[i - 1] + y[i], 1, 0, 100000); dp[i] = segmentTree::query(a[i], 1, 0, 100000); } printf("%lld\n", dp[n]); return 0; }