Submission #1125022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125022		fryingduc	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	33 ms	7956 KiB

kyoto

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n, m, a[maxn], b[maxn];
struct point_t {
  long long x, y;
  bool operator<(const point_t &o) {
    return (x != o.x ? x < o.x : y < o.y);
  }
  point_t operator-(const point_t &o) const {
    return {x - o.x, y - o.y};
  }
  long long operator*(const point_t &o) const {
    return 1ll * x * o.y - 1ll * y * o.x;
  }
};
long long cross(const point_t &a, const point_t &b, const point_t &c) {
  return (b - a) * (c - b);
}
bool ccw(const point_t &a, const point_t &b, const point_t &c) {
  return cross(a, b, c) > 0;
}
bool cw(const point_t &a, const point_t &b, const point_t &c) {
  return cross(a, b, c) < 0;
}
void make_hull(vector<point_t> &a) {
  sort(a.begin(), a.end());
  vector<point_t> hull;
  for(int i = 0; i < (int)a.size(); ++i) {
    while((int)hull.size() > 1 and cw(hull[(int)hull.size() - 2], hull.back(), a[i])) {
      hull.pop_back();
    }
    hull.push_back(a[i]);
  }
  a.swap(hull);
  hull.clear();
}
void solve() {
  cin >> n >> m;
  vector<point_t> ha;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    ha.push_back({i, a[i]});
  }
  make_hull(ha);
  
  vector<point_t> hb;
  for(int i = 1; i <= m; ++i) {
    cin >> b[i];
    hb.push_back({i, b[i]});
  }
  make_hull(hb);
  
  // it is optimal to approach smaller ai, bi as i grows
  // we are approaching the global minimum from both sides
  // -> lower hull
  
  
  // assume we are at point (x1, y1) with values (a1, b1)
  // we need to find the optimal rotation 
  // there are 2 ways to get to (x2, y2) to achieve the value (a2, b2)
  // comparing a1 * (y2 - y1) + b2 * (x2 - x1) with a2 * (y2 - y1) + b1 * (x2 - x1)
  // (a1 - a2) / (x2 - x1) with (b1 - b2) / (y2 - y1)
  // this is the cross product of vector (ha(i), ha(i + 1)) and (hb(i), hb(i + 1))
  
  int l = 0, r = 0;
  long long res = 0;
  while(l + 1 < (int)ha.size() || r + 1 < (int)hb.size()) {
    if(l + 1 < (int)ha.size() and r + 1 < (int)hb.size()) {
      if((ha[l] - ha[l + 1]) * (hb[r] - hb[r + 1]) > 0) {
        res += 1ll * (ha[l + 1].x - ha[l].x) * hb[r].y;
        ++l;
      } else {
        res += 1ll * (hb[r + 1].x - hb[r].x) * ha[l].y;
        ++r;
      }
    } else if(l + 1 < (int)ha.size()) {
      res += 1ll * (ha[l + 1].x - ha[l].x) * hb[r].y;
      ++l;
    } else {
      res += 1ll * (hb[r + 1].x - hb[r].x) * ha[l].y;
      ++r;
    }
  }
  cout << res;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60