Submission #366410

#	Time	Username	Problem	Language	Result	Execution time	Memory
366410		wleung_bvg	Planine (COCI21_planine)	C++17	0 / 110	2066 ms	49052 KiB

Main

#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;using ld=long double;constexpr const char nl='\n',sp=' ';

template <class T> T abs(T a) { return a >= 0 ? a : -a; }

template <class T> T gcd(T a, T b) { return b == 0 ? abs(a) : gcd(b, a % b); }

template <class T> struct Fraction {
  // static_assert(is_integral<T>::value, "T must be an integral type");
  using F = Fraction<T>; T num, den;
  Fraction(T num = T(), T den = T(1)) : num(num), den(den) {}
  F reduce() const {
    T g = gcd(num, den);
    return den >= 0 ? F(num / g, den / g) : F(-num / g, -den / g);
  }
  F operator + (const F &f) const { return F(*this) += f; }
  F &operator += (const F &f) {
    num = (num * f.den + f.num * den); den = den * f.den; return *this;
  }
  F operator - (const F &f) const { return F(*this) -= f; }
  F &operator -= (const F &f) {
    num = (num * f.den - f.num * den); den = den * f.den; return *this;
  }
  F operator + () const { return *this; }
  F operator - () const { return F(-num, den); }
  F operator * (const F &f) const { return F(*this) *= f; }
  F &operator *= (const F &f) {
    num = num * f.num; den = den * f.den; return *this;
  }
  F operator / (const F &f) const { return F(*this) /= f; }
  F &operator /= (const F &f) {
    T t_num = num * f.den, t_den = den * f.num; num = t_num; den = t_den;
    return *this;
  }
  bool operator < (const F &f) const {
    F a = reduce(), b = f.reduce(); return a.num * b.den < b.num * a.den;
  }
  bool operator <= (const F &f) const { return !(f < *this); }
  bool operator > (const F &f) const { return f < *this; }
  bool operator >= (const F &f) const { return !(*this < f); }
  bool operator == (const F &f) const { return !(*this < f) && !(f < *this); }
  bool operator != (const F &f) const { return !(*this == f); }
};

template <
    class It,
    class Cmp = less<typename iterator_traits<It>::value_type::first_type>>
It intervalSchedulingMax(It st, It en, Cmp cmp = Cmp()) {
  using Pair = typename iterator_traits<It>::value_type;
  assert(is_sorted(st, en, [&] (const Pair &a, const Pair &b) {
    return cmp(a.second, b.second);
  }));
  It cur = st; for (It l = st, r = st; l != en; l = r, cur++) {
    *cur = *l; for (r = l + 1; r != en && !cmp(cur->second, r->first); r++);
  }
  return cur;
}

using F = Fraction<__int128_t>;

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // freopen("err.txt", "w", stderr);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N;
  ll H;
  cin >> N >> H;
  vector<ll> X(N), Y(N);
  for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];
  vector<pair<F, F>> intervals;
  auto getX = [&] (int i, int j) {
    return F(H - Y[i]) / F(Y[j] - Y[i], X[j] - X[i]) + F(X[i]);
  };
  for (int i = 2; i < N - 2; i += 2) intervals.emplace_back(getX(i, i - 1), getX(i, i + 1));
  sort(intervals.begin(), intervals.end(), [&] (const pair<F, F> &a, const pair<F, F> &b) {
    return a.second < b.second;
  });
  cout << intervalSchedulingMax(intervals.begin(), intervals.end()) - intervals.begin() << nl;
  return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60