結果

問題 No.2114 01 Matching
ユーザー hashiryohashiryo
提出日時 2023-10-30 17:34:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 381 ms / 5,000 ms
コード長 10,995 bytes
コンパイル時間 3,834 ms
コンパイル使用メモリ 225,328 KB
実行使用メモリ 52,608 KB
最終ジャッジ日時 2023-10-30 17:34:33
合計ジャッジ時間 19,662 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 132 ms
8,336 KB
testcase_03 AC 46 ms
13,116 KB
testcase_04 AC 72 ms
17,464 KB
testcase_05 AC 51 ms
7,652 KB
testcase_06 AC 105 ms
7,288 KB
testcase_07 AC 59 ms
5,344 KB
testcase_08 AC 156 ms
9,700 KB
testcase_09 AC 113 ms
7,992 KB
testcase_10 AC 58 ms
5,388 KB
testcase_11 AC 336 ms
52,608 KB
testcase_12 AC 334 ms
52,608 KB
testcase_13 AC 128 ms
16,728 KB
testcase_14 AC 117 ms
10,788 KB
testcase_15 AC 107 ms
10,788 KB
testcase_16 AC 202 ms
11,316 KB
testcase_17 AC 101 ms
6,764 KB
testcase_18 AC 97 ms
9,132 KB
testcase_19 AC 131 ms
12,568 KB
testcase_20 AC 352 ms
52,608 KB
testcase_21 AC 195 ms
13,260 KB
testcase_22 AC 98 ms
5,380 KB
testcase_23 AC 126 ms
12,424 KB
testcase_24 AC 31 ms
6,784 KB
testcase_25 AC 32 ms
9,176 KB
testcase_26 AC 349 ms
52,608 KB
testcase_27 AC 348 ms
52,608 KB
testcase_28 AC 193 ms
30,036 KB
testcase_29 AC 347 ms
52,608 KB
testcase_30 AC 106 ms
6,652 KB
testcase_31 AC 361 ms
52,608 KB
testcase_32 AC 147 ms
8,724 KB
testcase_33 AC 58 ms
5,332 KB
testcase_34 AC 81 ms
6,184 KB
testcase_35 AC 114 ms
22,480 KB
testcase_36 AC 357 ms
52,608 KB
testcase_37 AC 117 ms
8,324 KB
testcase_38 AC 59 ms
5,472 KB
testcase_39 AC 58 ms
7,136 KB
testcase_40 AC 118 ms
21,956 KB
testcase_41 AC 130 ms
8,160 KB
testcase_42 AC 107 ms
10,492 KB
testcase_43 AC 145 ms
7,312 KB
testcase_44 AC 204 ms
12,212 KB
testcase_45 AC 345 ms
52,356 KB
testcase_46 AC 40 ms
6,868 KB
testcase_47 AC 350 ms
52,352 KB
testcase_48 AC 381 ms
52,608 KB
testcase_49 AC 130 ms
14,816 KB
testcase_50 AC 51 ms
4,904 KB
testcase_51 AC 58 ms
5,332 KB
testcase_52 AC 154 ms
22,616 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
#define checkpoint() (void(0))
#define debug(...) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
template <std::size_t NODE_SIZE= 1 << 22> class PiecewiseLinearConvexfunction {
 using i64= long long;
 using i128= __int128_t;
 using node_id= int;
 static constexpr i64 INF= 1ll << 41;
 template <class Int> static inline std::string str(Int x) {
  if (x >= INF) return "inf";
  if (x <= -INF) return "-inf";
  std::stringstream ss;
  ss << x;
  return ss.str();
 }
 struct Node {
  node_id ch[2], par;
  int sz;
  i64 dx, slope, laz, x;
  i128 y;
 };
 friend std::ostream &operator<<(std::ostream &os, Node *t) {
  if (!t) return os << "nullptr";
  return os << "{dx:" << str(t->dx) << ",slope:" << str(t->slope) << ",x:" << str(t->x) << ",y:" << str(t->y) << ",laz:" << str(t->laz) << "}";
 }
 static inline Node ns[NODE_SIZE];
 static inline node_id ni= 1;
 static inline node_id new_node() { return ni++; }
 static inline node_id new_node(i64 dx, i64 slope) { return ns[ni].ch[0]= ns[ni].ch[1]= ns[ni].par= ns[ni].laz= 0, ns[ni].y= i128(ns[ni].x= ns[ni].dx= dx) * (ns[ni].slope= slope), ns[ni].sz= 1, ni++; }
 static inline void propagate(node_id i, i64 a) {
  if (i) ns[i].slope+= a, ns[i].laz+= a, ns[i].y+= i128(a) * ns[i].x;
 }
 static inline void push(node_id i) {
  if (ns[i].laz) propagate(ns[i].ch[0], ns[i].laz), propagate(ns[i].ch[1], ns[i].laz), ns[i].laz= 0;
 }
 static inline void update(node_id i) {
  ns[i].sz= 1, ns[i].x= ns[i].dx, ns[i].y= i128(ns[i].slope) * ns[i].dx;
  if (int j= ns[i].ch[0]; j) ns[i].sz+= ns[j].sz, ns[i].x+= ns[j].x, ns[i].y+= ns[j].y;
  if (int j= ns[i].ch[1]; j) ns[i].sz+= ns[j].sz, ns[i].x+= ns[j].x, ns[i].y+= ns[j].y;
 }
 static inline int dir(node_id i) { return ns[ns[i].par].ch[1] == i; }
 static inline void rot(node_id i) {
  node_id p= ns[i].par;
  int d= dir(i);
  if ((ns[p].ch[d]= ns[i].ch[!d])) ns[ns[p].ch[d]].par= p;
  ns[i].ch[!d]= p;
  if ((ns[i].par= ns[p].par)) ns[ns[p].par].ch[dir(p)]= i;
  ns[p].par= i, update(p);
 }
 static inline void splay(node_id i) {
  for (node_id p= ns[i].par; p; rot(i), p= ns[i].par)
   if (node_id pp= ns[p].par; pp) rot(dir(i) == dir(p) ? p : i);
  update(i);
 }
 static inline void slope_search(node_id &i, i64 k) {
  for (node_id s;; i= s) {
   push(i);
   i64 tmp= ns[i].slope;
   if (tmp == k) break;
   if (s= ns[i].ch[tmp < k]; !s) break;
  }
  splay(i);
 }
 static inline void x_search(node_id &i, i64 x) {
  for (bool c;; i= ns[i].ch[c]) {
   push(i);
   i64 l= ns[i].ch[0] ? ns[ns[i].ch[0]].x : 0, r= l + ns[i].dx;
   if (l <= x && x <= r) return splay(i);
   if ((c= (r < x))) x-= r;
  }
 }
 static inline void add(node_id i, i64 &x, i64 &p, PiecewiseLinearConvexfunction &f) {
  if (!i) return;
  push(i);
  add(ns[i].ch[0], x, p, f);
  f.add_ax_bx_c(0, ns[i].slope - p, x);
  x+= ns[i].dx, p= ns[i].slope;
  add(ns[i].ch[1], x, p, f);
 }
 static inline void debugoutput(node_id i, int d) {
  if (!i) return;
  push(i);
  debugoutput(ns[i].ch[0], d + 1);
  for (int i= 0; i < d; ++i) std::cerr << "   ";
  std::cerr << "■ " << (i ? ns + i : nullptr) << '\n';
  debugoutput(ns[i].ch[1], d + 1);
 }
 node_id root;
 i64 lx, lslope;
 i128 ly;
 void chmin_sliding_window(i64 a) {
  if (!a) return;
  assert(a > 0);
  if (root) {
   slope_search(root, 0);
   if (ns[root].slope) {
    node_id i= new_node(a, 0);
    bool c= ns[root].slope < 0;
    if ((ns[i].ch[c]= ns[root].ch[c])) ns[ns[i].ch[c]].par= i;
    update(i), ns[root].ch[c]= i, ns[i].par= root;
   } else ns[root].dx+= a;
   update(root);
  } else if (lslope >= 0) lx+= a;
  else root= new_node(a, 0);
 }
public:
 static inline void clear() { ni= 1; }
 void debugoutput() { debugoutput(root, 0); }
 i64 upper_bound() { return lx + (root ? ns[root].x : 0); }
 // f(x) := 0
 PiecewiseLinearConvexfunction(): root(0), lx(INF * 2), lslope(0), ly(0) {}
 // f(x) + c
 void add_const(i128 c) { ly+= c; }
 // f(x) + ax+c
 void add_linear(i64 a, i128 c= 0) { lslope+= a, ly+= i128(a) * lx + c, propagate(root, a); }
 // f(x-a)
 void shift(i64 a) { lx+= a; }
 // f(x) + a * max{x-c, 0}
 void add_relu(i64 a, i64 c) {
  if (!a) return;
  assert(a > 0);
  if (c < lx) {
   if (lslope < -INF) return add_linear(a, -i128(a) * c);
   node_id i= new_node(lx - c, lslope);
   if (root) x_search(root, 0), ns[root].ch[0]= i, ns[i].par= root, update(root);
   else root= i;
   ly-= ns[i].y, lx= c, propagate(root, a);
   return;
  }
  if (upper_bound() <= c) return;
  c-= lx, x_search(root, c);
  i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0, r= l + ns[root].dx;
  if (l == c) {
   node_id i= ns[root].ch[0];
   ns[root].ch[0]= 0, propagate(root, a), push(root), ns[root].ch[0]= i;
  } else if (r == c) {
   propagate(ns[root].ch[1], a);
  } else {
   node_id i= new_node(r - c, ns[root].slope);
   if ((ns[i].ch[1]= ns[root].ch[1])) ns[ns[i].ch[1]].par= i;
   update(i), propagate(i, a), ns[root].ch[1]= i, ns[i].par= root, ns[root].dx= c - l, update(root);
  }
 }
 // f(x) + a * min{x-c,0} + b * max{x-c,0}
 void add_ax_bx_c(i64 a, i64 b, i64 c) { assert(a <= b), add_linear(a, -i128(a) * c), add_relu(b - a, c); }
 // f(x) + a * |x-c|
 void add_abs(i64 a, i64 c) { add_ax_bx_c(-a, a, c); }
 // ∞ if x>a else f(x)
 void chinfty_right(i64 a= 0) {
  assert(lx <= a || lslope >= -INF);
  if (root) {
   if (a-= lx; ns[root].x <= a) return;
   x_search(root, a);
   i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0;
   if (l == a) root= ns[root].ch[0], ns[root].par= 0;
   else ns[root].dx= a - l, ns[root].ch[1]= 0, update(root);
  } else lx= a;
 }
 // ∞ if x<a else f(x)
 void chinfty_left(i64 a= 0) {
  assert(a <= upper_bound());
  if (a-= lx; a < 0) {
   if (lslope < -INF) return;
   node_id i= new_node(-a, lslope);
   if (root) x_search(root, 0), ns[root].ch[0]= i, ns[i].par= root, update(root);
   else root= i;
   ly-= ns[i].y;
  } else if (a > 0) {
   assert(root);
   x_search(root, a);
   i64 r= ns[root].dx;
   if (int i= ns[root].ch[0]; i) ly+= ns[i].y + i128(a - ns[i].x) * ns[root].slope, r+= ns[i].x;
   else ly+= i128(a) * ns[root].slope;
   if (r == a) root= ns[root].ch[1], ns[root].par= 0;
   else ns[root].dx= r - a, ns[root].ch[0]= 0, update(root);
  }
  lx+= a, lslope= -INF * 2;
 }
 // min_{y<=x} f(y)
 void cumulative_chmin() {
  assert(lslope <= 0);
  if (root) {
   slope_search(root, 0);
   if (ns[root].slope < 0) {
    if (!ns[root].ch[1]) ns[root].ch[1]= new_node();
    node_id i= ns[root].ch[1];
    ns[i].sz= 1, ns[i].x= ns[i].dx= INF * 2, ns[i].slope= ns[i].ch[0]= ns[i].ch[1]= ns[i].laz= ns[i].y= 0, ns[i].par= root;
   } else ns[root].ch[1]= 0, ns[root].dx= INF * 2, ns[root].slope= 0;
   update(root);
  } else if (lslope) root= new_node(INF * 2, 0);
  else lx= INF * 2;
 }
 // min_{y<=x ∧ y<=a} f(y)
 void cumulative_chmin_with_condition(i64 a) { chinfty_right(a), cumulative_chmin(); }
 // min_{y>=x} f(y)
 void cumulative_chmin_rev() {
  if (root) {
   slope_search(root, 0);
   i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0, r= l + ns[root].dx, x= ns[root].slope > 0 ? l : r;
   if (int i= ns[root].ch[0]; i) ly+= ns[i].y + i128(x - ns[i].x) * ns[root].slope;
   else ly+= i128(x) * ns[root].slope;
   if (ns[root].slope > 0) ns[root].ch[0]= 0, update(root);
   else root= ns[root].ch[1], ns[root].par= 0;
   lx+= x;
  }
  lslope= 0;
 }
 // min_{y>=x ∧ y>=a} f(y)
 void cumulative_chmin_rev_with_condition(i64 a) { chinfty_left(a), cumulative_chmin_rev(); }
 // min_{x-b<=y<=x-a} f(y)
 void chmin_sliding_window(i64 a, i64 b) { assert(a <= b), shift(a), chmin_sliding_window(b - a); }
 // inf_y { f(x-y) + ( a * min{y-c,0} + b * max{y-c,0} ) }
 void convex_convolution_with_ax_bx_c(i64 a, i64 b, i64 c) { assert(a <= b), shift(c), add_linear(-a), cumulative_chmin_rev(), add_linear(a), add_linear(-b), cumulative_chmin(), add_linear(b); }
 // inf_y { f(x-y) + a |y-c| }
 void convex_convolution_with_abs(i64 a, i64 c) { convex_convolution_with_ax_bx_c(-a, a, c); }
 std::array<i64, 2> argmin() {
  assert(lslope <= 0);
  if (!lslope) return std::array{-INF, lx};
  if (!root) return std::array{lx, lx};
  slope_search(root, 0);
  i64 l= lx + (ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0), r= l + ns[root].dx;
  if (ns[root].slope == 0) return {l, r};
  return ns[root].slope < 0 ? std::array{r, r} : std::array{l, l};
 }
 i64 min() { return eval(argmin()[1]); }
 i64 eval(i64 x) {
  if (x < lx && lslope < -INF) return INF;
  if (x <= lx) return ly + i128(x - lx) * lslope;
  if (!root) return INF;
  if (x-= lx; ns[root].x < x) return INF;
  x_search(root, x);
  if (int i= ns[root].ch[0]; i) return ly + ns[i].y + i128(x - ns[i].x) * ns[root].slope;
  return ly + i128(x) * ns[root].slope;
 }
 i64 operator()(i64 x) { return eval(x); }
 int size() { return root ? ns[root].sz : 0; }
 // destructive
 PiecewiseLinearConvexfunction operator+(PiecewiseLinearConvexfunction &r) {
  if (size() > r.size()) std::swap(*this, r);
  if (lslope < -INF) r.chinfty_left(lx);
  else r.add_ax_bx_c(lslope, 0, lx);
  r.chinfty_right(upper_bound());
  long long x= lx, p= 0;
  add(root, x, p, r), r.add_const(ly);
  return r;
 }
 // destructive
 PiecewiseLinearConvexfunction &operator+=(PiecewiseLinearConvexfunction &r) { return *this= *this + r; }
};
template <class T> auto compress(std::vector<T> &v) {
 return std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end()), [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };
}
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using PLCF= PiecewiseLinearConvexfunction<>;
 int N, M, K;
 cin >> N >> M >> K;
 unordered_map<int, array<vector<int>, 2>> mp;
 for (int i= 0; i < N; ++i) {
  int B;
  cin >> B;
  mp[B % K][N >= M].push_back(B / K);
 }
 for (int i= 0; i < M; ++i) {
  int R;
  cin >> R;
  mp[R % K][N < M].push_back(R / K);
 }
 long long ans= 0;
 for (auto &&[_, arr]: mp) {
  auto &&[A, B]= arr;
  if (A.size() > B.size()) return cout << -1 << '\n', 0;
  vector<int> vec(A);
  for (int i: B) vec.push_back(i);
  auto id= compress(vec);
  int n= vec.size();
  vector<int> a(n), b(n);
  for (int i: A) ++a[id(i)];
  for (int i: B) ++b[id(i)];
  PLCF f;
  f.chinfty_left(), f.chinfty_right();
  for (int i= 0; i < n; ++i) {
   f.cumulative_chmin();
   f.shift(a[i] - b[i]);
   if (i < n - 1) f.add_abs(vec[i + 1] - vec[i], 0);
  }
  ans+= f.eval(0);
  PLCF::clear();
 }
 cout << ans << '\n';
 return 0;
}
0