結果
問題 | No.704 ゴミ拾い Medium |
ユーザー |
![]() |
提出日時 | 2018-11-09 09:05:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,704 bytes |
コンパイル時間 | 1,125 ms |
コンパイル使用メモリ | 98,868 KB |
実行使用メモリ | 37,352 KB |
最終ジャッジ日時 | 2024-11-21 05:04:44 |
合計ジャッジ時間 | 13,052 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 WA * 14 |
ソースコード
#include<iostream>#include<string>#include<vector>#include<queue>#include<stack>#include<map>#include<set>#include<algorithm>#include<functional>#include<cstdio>#include<cstdlib>#include<cmath>#include<cassert>#include<ctime>#include<utility>using namespace std;#define mind(a,b) (a>b?b:a)#define maxd(a,b) (a>b?a:b)#define absd(x) (x<0?-(x):x)#define pow2(x) ((x)*(x))#define rep(i,n) for(int i=0; i<n; ++i)#define repr(i,n) for(int i=n-1; i>=0; --i)#define repl(i,s,n) for(int i=s; i<=n; ++i)#define replr(i,s,n) for(int i=n; i>=s; --i)#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)#define repe(e,obj) for(auto e : obj)#define SP << " " <<#define COL << " : " <<#define COM << ", " <<#define ARR << " -> " <<#define PNT(STR) cout << STR << endl#define POS(X,Y) "(" << X << ", " << Y << ")"#define DEB(A) " (" << #A << ") " << A#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl#define ALL(V) (V).begin(), (V).end()#define INF 1000000007#define INFLL 1000000000000000007LL#define EPS 1e-9typedef unsigned int uint;typedef unsigned long ulong;typedef unsigned long long ull;typedef long long ll;typedef long double ld;#define P_TYPE inttypedef pair<P_TYPE, P_TYPE> P;typedef pair<P, P_TYPE> PI;typedef pair<P_TYPE, P> IP;typedef pair<P, P> PP;typedef priority_queue<P, vector<P>, greater<P> > pvqueue;#define N 300004class LiChaoTree {int n;ll xs[4*N];ll p[4*N], q[4*N];bool u[4*N];void _add_line(ll a, ll b, int k, int l, int r) {while(r-l > 0) {int m = (l + r) >> 1;if(!u[k]) {p[k] = a; q[k] = b;u[k] = true;return;}ll lx = xs[l], mx = xs[m], rx = xs[r-1];ll pk = p[k], qk = q[k];bool left = (a*lx+b < pk*lx+qk);bool mid = (a*mx+b < pk*mx+qk);bool right = (a*rx+b < pk*rx+qk);if(left && right) {p[k] = a; q[k] = b;return;}if(!left && !right) {return;}if(mid) {swap(p[k], a);swap(q[k], b);}if(left != mid) {k = 2*k+1; r = m;} else {k = 2*k+2; l = m;}}}ll _query(int k, ll x) {k += n - 1;ll s = u[k] ? p[k]*x+q[k] : INFLL;while(k > 0) {k = (k - 1) / 2;if(u[k]) {ll r = p[k]*x+q[k];s = mind(s, r);}}return s;}public:LiChaoTree(int n0, ll ps[N]) {n = 1;while(n < n0) n <<= 1;rep(i, 2*n) u[i] = false;rep(i, n0) xs[i] = ps[i];repl(i, n0, 2*n-1) xs[i] = INF;}void add_line(ll a, ll b) {_add_line(a, b, 0, 0, n);}void add_segment_line(ll a, ll b, int l, int r) {ll l0 = l + n, r0 = r + n;ll s0 = l, t0 = r, sz = 1;while(l0 < r0) {if(r0 & 1) {--r0; t0 -= sz;_add_line(a, b, r0-1, t0, t0+sz);}if(l0 & 1) {_add_line(a, b, l0-1, s0, s0+sz);++l0; s0 += sz;}l0 >>= 1; r0 >>= 1;sz <<= 1;}}ll query(int i) {return _query(i, xs[i]);}};int n;ll a[N], a0[N], x[N], y[N];set<ll> x0;map<ll, int> z;int main() {cin >> n;rep(i, n) cin >> a[i];rep(i, n) cin >> x[i];rep(i, n) cin >> y[i];rep(i, n) x0.insert(a[i]);int idx = 0;repe(v, x0) {a0[idx] = v;z[v] = idx++;}set<ll>::iterator it = x0.begin();LiChaoTree lct(x0.size(), a0);ll v = 0;int j = -1;rep(i, n) {while(it != x0.end() && (*it) < x[i]) {++it;j += 1;}lct.add_segment_line(-1, x[i]+y[i]+v, 0, j+1);lct.add_segment_line(1, -x[i]+y[i]+v, j+1, n);v = lct.query(z[a[i]]);}cout << v << endl;return 0;}