結果
問題 |
No.704 ゴミ拾い Medium
|
ユーザー |
![]() |
提出日時 | 2025-03-21 19:48:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,078 bytes |
コンパイル時間 | 1,803 ms |
コンパイル使用メモリ | 167,540 KB |
実行使用メモリ | 19,528 KB |
最終ジャッジ日時 | 2025-03-21 19:48:23 |
合計ジャッジ時間 | 7,968 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 14 WA * 30 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:53:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 53 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:54:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 54 | for (int i = 1;i <= n;++i) scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:55:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 55 | for (int i = 1;i <= n;++i) scanf("%d", &x[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:56:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 56 | for (int i = 1;i <= n;++i) scanf("%d", &y[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
/* address:https://vjudge.net/problem/Yukicoder-704 */ /* address:https://vjudge.net/problem/Yukicoder-703 AC 2025/3/21 16:02 */ #include<bits/stdc++.h> using namespace std; const int N = 6e5 + 5; const int V = 1e5 + 5; struct line { int k, b; }li[N]; struct LiChaoSegmentTree { #define ls (id << 1) #define rs (id << 1 | 1) #define mid (l + r >> 1) int idl[V << 2]; inline int cmp(int i, int j, int x) { int y0 = li[i].k * x + li[i].b, y1 = li[j].k * x + li[j].b; if (y0 <= y1) return i; else return j; } inline void update(int id, int l, int r, int j) { int& i = idl[id]; if (i == j) return; if (cmp(i, j, mid) == j) swap(i, j); if (cmp(i, j, l) == j) update(ls, l, mid, j); if (cmp(i, j, r) == j) update(rs, mid + 1, r, j); } inline void modify(int id, int l, int r, int L, int R, int j) { if (l >= L && R >= r) { update(id, l, r, j); return; } if (L <= mid) modify(ls, l, mid, L, R, j); if (R > mid) modify(rs, mid + 1, r, L, R, j); } inline int query(int id, int l, int r, int x) { if (l == r) return idl[id]; int ret = 0; if (x <= mid) ret = query(ls, l, mid, x); else ret = query(rs, mid + 1, r, x); return cmp(ret, idl[id], x); } }LCSGT; int n; int a[N], x[N], y[N]; int dp[N]; 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]); li[0] = { -1, dp[0] }; li[1] = { 1, dp[0] }; LCSGT.modify(1, 0, V - 5, x[1] + 1, V - 5, 1); for (int i = 1;i <= n;++i) { int j = LCSGT.query(1, 0, V - 5, a[i]); dp[i] = abs(x[j + 2 >> 1] - a[i]) + y[j + 2 >> 1] + dp[j >> 1]; li[i << 1] = { -1, dp[i] }; li[i << 1 | 1] = { 1, dp[i] }; LCSGT.modify(1, 0, V - 5, 0, x[i + 1], i << 1); LCSGT.modify(1, 0, V - 5, x[i + 1] + 1, V - 5, i << 1 | 1); } printf("%d\n", dp[n]); return 0; }