#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(r->first, cur->second); 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 auto &a, const auto &b) {
return a.second < b.second;
});
cout << intervalSchedulingMax(intervals.begin(), intervals.end()) - intervals.begin() << nl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1128 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1128 KB |
Output is correct |
| 3 |
Correct |
19 ms |
1128 KB |
Output is correct |
| 4 |
Incorrect |
116 ms |
6112 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1128 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1128 KB |
Output is correct |
| 3 |
Correct |
19 ms |
1128 KB |
Output is correct |
| 4 |
Incorrect |
116 ms |
6112 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
