Submission #512424

#	Time	Username	Problem	Language	Result	Execution time	Memory
512424		kartel	Planine (COCI21_planine)	C++14	0 / 110	24 ms	1612 KiB

Main

#include <bits/stdc++.h>
#define blue 0
#define red 1
#define purple 2
#define pb push_back
#define F first
#define S second
#define sz(x) (int)x.size()
using namespace std;
typedef long long ll;
typedef long double ld;

struct node {
    ld l, r;
    int f;

    node() {}
    node(ld l, ld r, ll f) : l(l), r(r), f(f) {}
};

const int N = 1e6 + 500;
const ld eps = 1e-9;

node t[4 * N];
int D[4 * N];
vector <ld> lft, rgt;
ll x[N], y[N];
int n, h, f[N];

void push(int v) {
    if (D[v] != 1e9) {
        D[v * 2] = min(D[v * 2], D[v]);
        D[v * 2 + 1] = min(D[v * 2 + 1], D[v]);
        t[v].f = min(t[v].f, D[v]);
        D[v] = 1e9;
    }
}

void build(int v, int l, int r) {
    D[v] = 1e9;
    if (l == r) {
        t[v] = node(lft[l], rgt[l], 1e9);
    } else {
        int md = (l + r) >> 1;
        build(v * 2, l, md);
        build(v * 2 + 1, md + 1, r);

        t[v].f = min(t[v * 2].f, t[v * 2 + 1].f);
        t[v].l = max(t[v * 2].l, t[v * 2 + 1].l);
        t[v].r = min(t[v * 2].r, t[v * 2 + 1].r);
    }
}

ll getl(int v, int l, int r, int tl, int tr) {
    if (l > r || tl > tr || tl > r || l > tr) {
        return -1e18;
    }
    if (l >= tl && r <= tr) {
        return t[v].l;
    }
    int md = (l + r) >> 1;
    return max(getl(v * 2, l, md, tl, tr), getl(v * 2 + 1, md + 1, r, tl, tr));
}

ll getr(int v, int l, int r, int tl, int tr) {
    if (l > r || tl > tr || tl > r || l > tr) {
        return 1e18;
    }

    if (l >= tl && r <= tr) {
        return t[v].r;
    }
    int md = (l + r) >> 1;
    return min(getr(v * 2, l, md, tl, tr), getr(v * 2 + 1, md + 1, r, tl, tr));
}

ll getf(int v, int l, int r, int ps) {
    push(v);
    if (l == r) {
        return t[v].f;
    } else {
        int md = (l + r) >> 1, cur;
        if (ps <= md) {
            return getf(v * 2, l, md, ps);
        } else {
            return getf(v * 2 + 1, md + 1, r, ps);
        }
    }
}

void upd(int v, int l, int r, int tl, int tr, int val) {
    push(v);
    if (l > r || tl > tr || tl > r || l > tr) {
        return;
    }
    if (l >= tl && r <= tr) {
        D[v] = min(D[v], val);
        push(v);
        return;
    }
    int md = (l + r) >> 1;
    upd(v * 2, l, md, tl, tr, val);
    upd(v * 2 + 1, md + 1, r, tl, tr, val);
}

int main() {
    cerr.precision(9);
    cerr << fixed;
    cin >> n >> h;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
//    if (n == 3) {
//        cout << "0";
//        return 0;
//    }
    for (int i = 3; i < n; i += 2) {
        ld k = ld(y[i - 1] - y[i]) / ld(x[i - 1] - x[i]);
        ld b = ld(y[i]) - k * x[i];
//        cerr << k << " " << b << el;
        lft.pb((h - b) / k);

        k = ld(y[i] - y[i + 1]) / ld(x[i] - x[i + 1]);
        b = ld(y[i]) - k * x[i];
//        cerr << k << " " << b << el;
        rgt.pb((h - b) / k);
    }
    n >>= 1; n--;
    lft.pb(-1e18);
    lft.pb(-1e18);
    rgt.pb(1e18);
    rgt.pb(1e18);
    build(1, 0, n + 1);

    f[0] = 0;
    upd(1, 0, n + 1, 0, 0, 0);
    for (int i = 0; i < n; i++) {
        int l = 0;
        int r = n - i;
        f[i] = getf(1, 0, n + 1, i);
        while (l < r) {
            int md = (l + r + 1) >> 1;
//            cerr << getl(1, 0, n + 1, i, i + md) << " " << getr(1, 0, n + 1, i, i + md) << "\n";
            if (getl(1, 0, n + 1, i, i + md) < getr(1, 0, n + 1, i, i + md) + eps) {
                l = md;
            } else {
                r = md - 1;
            }
        }
        upd(1, 0, n, i + 1, i + r + 1, f[i] + 1);
    }
    cout << getf(1, 0, n + 1, n + 1);
}

Compilation message (stderr)

Main.cpp: In function 'll getf(int, int, int, int)':
Main.cpp:82:32: warning: unused variable 'cur' [-Wunused-variable]
   82 |         int md = (l + r) >> 1, cur;
      |                                ^~~

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