#312784 (C++14) No.705 ゴミ拾い Hard

提出ソース

結果

問題	No.705 ゴミ拾い Hard
ユーザー	lumc_
提出日時	2019-01-26 02:48:38
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	149 ms / 1,500 ms
コード長	7,678 bytes
コンパイル時間	1,496 ms
コンパイル使用メモリ	123,312 KB
実行使用メモリ	12,780 KB
最終ジャッジ日時	2024-09-16 04:53:55
合計ジャッジ時間	5,763 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	3 ms 5,376 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	3 ms 5,376 KB
testcase_19	AC	3 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	3 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	3 ms 5,376 KB
testcase_24	AC	147 ms 12,716 KB
testcase_25	AC	148 ms 12,496 KB
testcase_26	AC	148 ms 12,640 KB
testcase_27	AC	149 ms 12,660 KB
testcase_28	AC	147 ms 12,672 KB
testcase_29	AC	149 ms 12,760 KB
testcase_30	AC	142 ms 12,644 KB
testcase_31	AC	132 ms 12,532 KB
testcase_32	AC	133 ms 12,504 KB
testcase_33	AC	57 ms 12,780 KB
testcase_34	AC	57 ms 12,664 KB
testcase_35	AC	120 ms 12,624 KB
testcase_36	AC	127 ms 12,672 KB
testcase_37	AC	119 ms 12,672 KB
testcase_38	AC	129 ms 12,640 KB
testcase_39	AC	136 ms 12,428 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	3 ms 5,376 KB
testcase_43	AC	141 ms 12,656 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// includes {{{
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// #undef DEBUG
// #define DEBUG
// DEBUG {{{
#include <array>
#include <deque>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <valarray>
#include <vector>
// clang-format off
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
template < class T > ostream &operator<<(ostream &o, const stack<T> &a) { o << "{"; for(auto tmp = a; tmp.size(); tmp.pop()) o << (a.size() == tmp.size() ? "" : ", ") << tmp.top(); o << "}"; return o; }
template <class T, class Container, class Compare > ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> a) { os << "{ (top) "; while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; }
template <class T, class Container > ostream &operator<<(ostream &os, queue<T, Container> a) { os << "{ "; while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; }
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT cerr
#endif
#if !defined(DEBUG_LEFT)
#define DEBUG_LEFT "\e[1;36m"
#endif
#if !defined(DEBUG_RIGHT)
#define DEBUG_RIGHT ":\e[m"
#endif
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);DEBUG_OUT<<DEBUG_LEFT<<__LINE__ << DEBUG_RIGHT << " " <<#__VA_ARGS__<<" = "<<__debug_tap<<endl;}()
template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << endl; } }
template < class T > inline void dump1D(T &d, size_t sizey) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << d[i] << (i + 1 == sizey ? "" : " "); } DEBUG_OUT << endl; }
template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { o << "{"; for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : ", ") << *ite; o << "}"; return o; }
#else
#define dump(...) (42)
#define dump2D(...) (42)
#define dump1D(...) (42)
template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : " ") << *ite; return o; }
#endif
// clang-format on
// }}}

constexpr int N = 3e5;
int n;
ll a[N];
ll x[N];
ll y[N];

// D(0) is given
// D(i) = f( min(0 <= j < i,  D(j) + w(j, i)) , i)
// w must satisfy Convex QI
// by default, f is identity function
// Convex QI Speedup {{{
#include <type_traits>
#include <vector>
#include <stack>
#include <cassert>
#include <functional>
template < class T, class W, class F = function< T(const T &) > >
auto ConvexQISpeedup(T d0, size_t n, const W &w,
                     const F &f = [](const T &t) { return t; }) {
#ifdef DEBUG
  static_assert(is_same< T, decltype(w(0, 0)) >::value, "T must equal to typeof w(...)");
  static_assert(is_same< T, decltype(f(T())) >::value, "T must equal to typeof f(...)");
#endif

  vector< T > D(n + 1);
  D[0] = d0;

  // C(j, i) = D(j) + w(j, i)
  auto C = [&](size_t j, size_t i) { return D[j] + w(j, i); };

  // search the first time to choose l rather than k
  // if w satisfies Closest Zero Property, you can speedup h
  auto h = [&](size_t l, size_t k) {
    assert(l < k && k < n + 1);
    size_t ok = n + 1, ng = k;
    while(ok - ng > 1) {
      size_t mid = (ok + ng) >> 1;
      if(C(l, mid) <= C(k, mid))
        ok = mid;
      else
        ng = mid;
    }
    return ok;
  };

  // (k, h) where k is index and h is the time to die
  stack< pair< size_t, size_t > > S;
  S.emplace(0, n + 1);
  for(size_t i = 1; i <= n; i++) {
    size_t j = S.top().first;
    if(C(i - 1, i) >= C(j, i))
      D[i] = f(C(j, i));
    else {
      D[i] = f(C(i - 1, i));
      while(S.size() &&
            C(i - 1, S.top().second - 1) < C(S.top().first, S.top().second - 1))
        S.pop();
      if(S.empty())
        S.emplace(i - 1, n + 1);
      else
        S.emplace(j, h(S.top().first, i - 1));
    }
    if(S.top().second == i + 1) S.pop();
  }
  return D;
}
// }}}

// D(0) is given
// D(i) = f( min(0 <= j < i,  D(j) + w(j, i)) , i)
// w must satisfy Concave QI = Monge
// by default, f is identity function
// Concave QI ( = Monge ) Speedup {{{
#include <type_traits>
#include <vector>
#include <deque>
#include <cassert>
#include <functional>
template < class T, class W, class F = function< T(const T &) > >
auto ConcaveQISpeedup(T d0, size_t n, const W &w,
                      const F &f = [](const T &t) { return t; }) {
#ifdef DEBUG
  static_assert(is_same< T, decltype(w(0, 0)) >::value, "T must equal to typeof w(...)");
  static_assert(is_same< T, decltype(f(T())) >::value, "T must equal to typeof f(...)");
#endif

  vector< T > D(n + 1);
  D[0] = d0;

  // C(j, i) = D(j) + w(j, i)
  auto C = [&](size_t j, size_t i) { return D[j] + w(j, i); };

  // search the first time to choose l rather than k
  // if w satisfies Closest Zero Property, you can speedup h
  auto h = [&](size_t l, size_t k) {
    assert(k < l && l < n + 1);
    size_t ok = n + 1, ng = l;
    while(ok - ng > 1) {
      size_t mid = (ok + ng) >> 1;
      if(C(l, mid) <= C(k, mid))
        ok = mid;
      else
        ng = mid;
    }
    return ok;
  };

  // (k, h) where k is index and h is the time to kill predecessor
  deque< pair< size_t, size_t > > Q;
  Q.emplace_back(0, 1);
  for(size_t i = 1; i <= n; i++) {
    assert(Q.size());
    size_t j = Q.front().first;
    if(C(i - 1, i) <= C(j, i)) {
      D[i] = f(C(i - 1, i));
      Q.clear();
      Q.emplace_back(i - 1, i + 1);
    } else {
      D[i] = f(C(j, i));
      while(Q.size() > 1 &&
            C(i - 1, Q.back().second) <= C(Q.back().first, Q.back().second))
        Q.pop_back();
      size_t k = h(i - 1, Q.back().first);
      if(k < n + 1) Q.emplace_back(i - 1, k);
      if(Q.size() > 1 && i + 1 == Q[1].second)
        Q.pop_front();
      else
        Q.front().second++;
    }
  }
  return D;
}
// }}}

#if 0
#convex QIについて
l < kについて "kではなくl ( = 小さい方) を選ぶ利点" はだんだん大きくなる

C(j, i) は i から j を選ぶときの損 のように考えればよい (損を最小化する)

#endif

constexpr ll inf = 1e18;

inline ll pow3(ll x) { return x * x * x; }

// 1-indexed
ll g(int k, int i) {
  assert(k < i);
  return pow3(abs(x[k] - a[i - 1])) + pow3(y[k]);
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> x[i];
  for(int i = 0; i < n; i++) cin >> y[i];

  cout << ConcaveQISpeedup< ll >(0, n, g)[n] << endl;
  return 0;
}

yukicoder

結果

テストケース

ソースコード