oj.uz

Submission #537802

# Submission time Handle Problem Language Result Execution time Memory
537802 2022-03-15T14:44:33 Z maomao90 Planine (COCI21_planine) C++17
110 / 110
 503 ms 56968 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 1000005

int n, h;
int x[MAXN], y[MAXN];
bool used[MAXN];
int ans;

struct frac {
    ll a, b;
    frac(): a(0), b(1) {}
    frac(ll _a): a(_a), b(1) {}
    frac(ll _a, ll _b): a(_a), b(_b) {
        if (b == 0) {
            a = LINF;
            b = 1;
            return;
        }
        ll g = __gcd(abs(a), abs(b));
        a /= g;
        b /= g;
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
    }
    frac operator+(const frac &o) const {
        return frac(a * o.b + b * o.a, b * o.b);
    }
    frac operator-(const frac &o) const {
        return *this + (-o);
    }
    frac operator-() const {
        return frac(-a, b);
    }
    bool operator<(const frac &o) const {
        assert(b > 0 && o.b > 0);
        return a * o.b < b * o.a;
    }
    bool operator>(const frac &o) const {
        assert(b > 0 && o.b > 0);
        return a * o.b > b * o.a;
    }
    bool operator==(const frac &o) const {
        return a == o.a && b == o.b;
    }
    bool operator<=(const frac &o) const {
        return *this == o || *this < o;
    }
    friend ostream& operator<<(ostream &os, const frac &o) {
        return os << o.a << '/' << o.b;
    }
};

struct Range {
    frac l, r;
    bool operator<(const Range &o) const {
        return r < o.r;
    }
};

frac l[MAXN], r[MAXN];
vector<Range> ranges;

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> h;
    REP (i, 0, n) {
        cin >> x[i] >> y[i];
    }
    REP (zz, 0, 2) {
        vi pts;
        REP (i, 1, n - 1) {
            auto ori = [&] (int a, int b, int c) {
                // b - a cross c - a
                ll x1 = x[b] - x[a], y1 = y[b] - y[a],
                x2 = x[c] - x[a], y2 = y[c] - y[a];
                return x1 * y2 - x2 * y1;
            };
            while (pts.size() >= 2 && ori(pts[pts.size() - 2], pts[pts.size() - 1], i) > 0) {
                pts.pop_back();
            }
            if (i % 2 == 0) {
                int j = pts.back();
                l[i] = frac(x[i]) - frac((ll) (x[i] - x[j]) * (h - y[i]), y[j] - y[i]);
            }
            pts.pb(i);
        }
        swap(l, r);
        REP (i, 0, n) {
            x[i] *= -1;
        }
        reverse(x, x + n);
        reverse(y, y + n);
    }
    REP (i, 0, n) {
        r[i] = -r[i];
    }
    reverse(r, r + n);
    for (int i = 2; i < n - 1; i += 2) {
        cerr << i << ": " << l[i] << ' ' << r[i] << '\n';
        ranges.pb((Range) {l[i], r[i]});
    }
    sort(ALL(ranges));
    REP (i, 0, ranges.size()) {
        if (used[i]) continue;
        frac x = ranges[i].r;
        ans++;
        REP (j, i, ranges.size()) {
            if (ranges[j].l <= x && x <= ranges[j].r) {
                used[j] = 1;
            } else {
                break;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}


/*
2: -6/1 2/3
4: -1/1 5/1
6: 2/1 8/1
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:13:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
  141 |     REP (i, 0, ranges.size()) {
      |          ~~~~~~~~~~~~~~~~~~~            
Main.cpp:141:5: note: in expansion of macro 'REP'
  141 |     REP (i, 0, ranges.size()) {
      |     ^~~
Main.cpp:13:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
  145 |         REP (j, i, ranges.size()) {
      |              ~~~~~~~~~~~~~~~~~~~        
Main.cpp:145:9: note: in expansion of macro 'REP'
  145 |         REP (j, i, ranges.size()) {
      |         ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 32072 KB Output is correct
2 Correct 22 ms 32148 KB Output is correct
3 Correct 24 ms 32156 KB Output is correct
4 Correct 46 ms 35016 KB Output is correct
5 Correct 57 ms 35012 KB Output is correct
6 Correct 62 ms 34976 KB Output is correct
7 Correct 304 ms 56380 KB Output is correct
8 Correct 402 ms 56360 KB Output is correct
9 Correct 493 ms 56324 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31640 KB Output is correct
2 Correct 18 ms 31676 KB Output is correct
3 Correct 18 ms 31544 KB Output is correct
4 Correct 21 ms 31668 KB Output is correct
5 Correct 20 ms 31572 KB Output is correct
6 Correct 19 ms 31712 KB Output is correct
7 Correct 18 ms 31668 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 32072 KB Output is correct
2 Correct 22 ms 32148 KB Output is correct
3 Correct 24 ms 32156 KB Output is correct
4 Correct 46 ms 35016 KB Output is correct
5 Correct 57 ms 35012 KB Output is correct
6 Correct 62 ms 34976 KB Output is correct
7 Correct 304 ms 56380 KB Output is correct
8 Correct 402 ms 56360 KB Output is correct
9 Correct 493 ms 56324 KB Output is correct
10 Correct 19 ms 31640 KB Output is correct
11 Correct 18 ms 31676 KB Output is correct
12 Correct 18 ms 31544 KB Output is correct
13 Correct 21 ms 31668 KB Output is correct
14 Correct 20 ms 31572 KB Output is correct
15 Correct 19 ms 31712 KB Output is correct
16 Correct 18 ms 31668 KB Output is correct
17 Correct 368 ms 56692 KB Output is correct
18 Correct 381 ms 56636 KB Output is correct
19 Correct 54 ms 34888 KB Output is correct
20 Correct 371 ms 56304 KB Output is correct
21 Correct 55 ms 34940 KB Output is correct
22 Correct 503 ms 56968 KB Output is correct
23 Correct 17 ms 31572 KB Output is correct
24 Correct 425 ms 56892 KB Output is correct
25 Correct 52 ms 34948 KB Output is correct
26 Correct 354 ms 56936 KB Output is correct
27 Correct 40 ms 33484 KB Output is correct