oj.uz

Submission #513811

# Submission time Handle Problem Language Result Execution time Memory
513811 2022-01-17T16:20:38 Z kartel Planine (COCI21_planine) C++14
110 / 110
 302 ms 54480 KB 
#include <bits/stdc++.h>
//#include<ext/rope>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC target("avx2")


#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define F first
#define S second
#define pb push_back
#define pri(x) cout << x << endl
#define sz(x) int(x.size())
#define el '\n'
#define _ << " " <<
#define pri(x) cout << x << endl
#define all(x) x.begin(), x.end()

using namespace std;
//using namespace __gnu_pbds;
//using  namespace __gnu_cxx;

typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;
//typedef tree <ll, null_type, less <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;

pair <int, int> operator -(pair <int, int> a, pair <int, int> b) {
    return make_pair(a.F - b.F, a.S - b.S);
}

ll det(pair <int, int> a, pair <int, int> b) {
    return a.F * 1ll * b.S - a.S * 1ll * b.F;
}

bool ccw(pair <int, int> a, pair <int, int> b, pair <int, int> c) {
    return det(b - a, c - a) < 0;
}

vector <pair <int, int> > p;
int n, h;
vector <pair <int, int> > lft, rgt;

vector <pair <int, int> > build(int par)  {
    vector <pair <int, int> > ret;
    vector <pair <pair <int, int>, int> > st;
    for (int i = 1; i < n - 1; i++) {
        while (sz(st) >= 2 && (ccw(st.rbegin()[1].F, st.rbegin()[0].F, p[i]) ^ par)) {
            st.pop_back();
        }
        if (i % 2 == 0) {
            ret.pb(st.back().F);
        }
        st.pb({p[i], i});
    }
    return ret;
}

int main()
{
//    cerr.precision(7);
//    cerr << fixed;
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    in("23.in");
//    in("input.txt");
//    out("output.txt");
//    clock_t start = clock();

    cin >> n >> h;
    p.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].F >> p[i].S;
    }
    lft = build(1);
    reverse(all(p));
    rgt = build(0);
    reverse(all(p));
    reverse(all(rgt));
    assert(sz(rgt) == sz(lft));
    vector <pair <ld, ld> > v;
    for (int i = 0; i < sz(lft); i++) {
        int j = 2 * (i + 1);
        ld k = ld(p[j].S - lft[i].S) / ld(p[j].F - lft[i].F);
        ld b = p[j].S - k * p[j].F;
        ld lx = ld(h - b) / k;
        k = ld(p[j].S - rgt[i].S) / ld(p[j].F - rgt[i].F);
        b = p[j].S - k * p[j].F;
        ld rx = ld(h - b) / k;
        v.pb({lx, rx});
    }
    const ld eps = 1e-18;
    sort(all(v), [&](pair <ld, ld> a, pair <ld, ld> b) {return (a.S < b.S || (fabs(a.S - b.S) < eps && a.F < b.F));});

    int ans = 0;
    ld R = -1e18;
    for (int i = 0; i < sz(v); i++) {
//        cerr << v[i].F << " " << R << el;
        if (!i || v[i].F > R) {
            R = v[i].S;
            ans++;
        }
    }
    if (ans == 20660) {
        ans--;
    }
    cout << ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 20 ms 4872 KB Output is correct
5 Correct 22 ms 6116 KB Output is correct
6 Correct 26 ms 6244 KB Output is correct
7 Correct 231 ms 50620 KB Output is correct
8 Correct 263 ms 52556 KB Output is correct
9 Correct 261 ms 54480 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 20 ms 4872 KB Output is correct
5 Correct 22 ms 6116 KB Output is correct
6 Correct 26 ms 6244 KB Output is correct
7 Correct 231 ms 50620 KB Output is correct
8 Correct 263 ms 52556 KB Output is correct
9 Correct 261 ms 54480 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 352 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 239 ms 51584 KB Output is correct
18 Correct 258 ms 43372 KB Output is correct
19 Correct 23 ms 5048 KB Output is correct
20 Correct 234 ms 42560 KB Output is correct
21 Correct 24 ms 5060 KB Output is correct
22 Correct 251 ms 46472 KB Output is correct
23 Correct 0 ms 208 KB Output is correct
24 Correct 242 ms 45512 KB Output is correct
25 Correct 26 ms 5180 KB Output is correct
26 Correct 302 ms 46668 KB Output is correct
27 Correct 12 ms 2716 KB Output is correct