Submission #1208491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208491		vasfor	Tri (CEOI09_tri)	C++20	20 / 100	553 ms	108424 KiB

tri

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pll = pair<long long, long long>;

struct pt {
    int x = 0;
    int y = 0;

    pt operator-(const pt& o) const {
        return {x - o.x, y - o.y};
    }

    ll vector_mul(const pt& o) const {
        return 1ll * x * o.y - 1ll * o.x * y;
    }
};

pll intersect_lines(pt L1, pt L2) {
    // f(t) = x + t * y
    // x1 + t * y1 == x2 + t * t2
    // t = (x2 - x1) / (y1 - y2)
    ll u = L2.x - L1.x;
    ll v = L1.y - L2.y;
    if (v < 0) u = -u, v = -v;
    return {u, v};
}

bool cmp(pll p1, pll p2) {
    return p1.first * p2.second < p2.first * p1.second;
}

struct CHT {
    vector<pt> st;

    CHT() = default;

    CHT(vector<pt> a) {
        sort(a.begin(), a.end(), [&](pt p1, pt p2) {
            if (p1.y != p2.y) return p1.y < p2.y;
            else return p1.x < p2.x;
        });
        for (auto p : a) {
            if (!st.empty() && st.back().y == p.y) {
                st.back().x = p.x;
                continue;
            }
            while ((int) st.size() >= 2) {
                pt L1 = st[(int) st.size() - 2];
                pt L2 = st[(int) st.size() - 1];
                auto x1 = intersect_lines(L1, L2);
                auto x2 = intersect_lines(L2, p);
                if (cmp(x1, x2)) break;
                else st.pop_back();
            }
            st.push_back(p);
        }
    }

    ll get_max(int p, int q) {
        // p * x + q * y -> max
        // p > 0
        // p * (x + (q / p) * y) -> max
        // arg = q / p
        assert(p > 0);
        pll x0 = {q, p};
        int bl = 0, br = (int) st.size(), bm;
        while (br - bl > 1) {
            bm = bl + (br - bl) / 2;
            pll x = intersect_lines(st[bm], st[bm + 1]);
            if (cmp(x0, x)) br = bm;
            else bl = bm;
        }
        ll max_value = -5e18;
        for (int di = -2; di <= 2; ++di) {
            int i = bl + di;
            if (i < 0 || i >= (int) st.size()) continue;
            ll tmp_value = 1ll * p * st[i].x + 1ll * q * st[i].y;
            if (tmp_value > max_value) {
                max_value = tmp_value;
            }
        }
        return max_value;
    }
};

struct RangeTree {
    int n = 0;
    vector<vector<pt>> pts;
    vector<CHT> cht_xy_pos, cht_xy_neg, cht_yx_pos, cht_yx_neg;

    RangeTree(const vector<pt>& a): n(a.size()), pts(4 * n), 
        cht_xy_pos(4 * n), cht_xy_neg(4 * n), cht_yx_pos(4 * n), cht_yx_neg(4 * n)
    {
        build(a, 1, 0, n - 1);
    }

    void build(const vector<pt>& a, int v, int tl, int tr) {
        if (tl == tr) {
            pts[v].push_back(a[tl]);
        } else {
            int tm = tl + (tr - tl) / 2;
            build(a, v << 1, tl, tm);
            build(a, v << 1 | 1, tm + 1, tr);

            {
                pts[v] = pts[v << 1];
                copy(pts[v << 1 | 1].begin(), pts[v << 1 | 1].end(), back_inserter(pts[v]));
            }
        }
        cht_xy_pos[v] = CHT(pts[v]);
        
        for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
        cht_xy_neg[v] = CHT(pts[v]);
        for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;

        for (auto& p : pts[v]) swap(p.x, p.y);

        cht_yx_pos[v] = CHT(pts[v]);
        
        for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
        cht_yx_neg[v] = CHT(pts[v]);
        for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
        
        for (auto& p : pts[v]) swap(p.x, p.y);
    }

    ll get_max(int v, int tl, int tr, int l, int r, int p, int q) {
        if (l <= tl && tr <= r) {
            if (p > 0) return cht_xy_pos[v].get_max(p, q);
            else if (p < 0) return cht_xy_neg[v].get_max(-p, -q);
            else {
                if (q > 0) return cht_yx_pos[v].get_max(q, p);
                else {
                    assert(q < 0);
                    return cht_yx_neg[v].get_max(-q, -p);
                }
            }
        } else {
            int tm = tl + (tr - tl) / 2;
            ll res = -5e18;
            if (l <= tm) {
                ll tmp = get_max(v << 1, tl, tm, l, r, p, q);
                if (tmp > res) res = tmp;
            }
            if (r > tm) {
                ll tmp = get_max(v << 1 | 1, tm + 1, tr, l, r, p, q);
                if (tmp > res) res = tmp;
            }
            return res;
        }
    }

    ll get_max(int l, int r, int p, int q) {
        // px + qy -> max
        return get_max(1, 0, n - 1, l, r, p, q);
    }
};

int main() {

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<pt> a(n);
    for (auto& p : a) cin >> p.x >> p.y;
    sort(a.begin(), a.end(), [&](pt p1, pt p2) {
        return p1.vector_mul(p2) > 0;
    });

    RangeTree rt(a);

    for (int it = 0; it < m; ++it) {
        pt l, r;
        cin >> l.x >> l.y;
        cin >> r.x >> r.y;
        if (l.vector_mul(r) < 0) swap(l, r);
        int ql, qr;
        if (l.vector_mul(a.back()) > 0) {
            int bl = -1, br = (int) a.size() - 1, bm;
            while (br - bl > 1) {
                bm = bl + (br - bl) / 2;
                if (l.vector_mul(a[bm]) > 0) br = bm;
                else bl = bm;
            }
            ql = br;
        }
        if (a.front().vector_mul(r) > 0) {
            int bl = 0, br = (int) a.size(), bm;
            while (br - bl > 1) {
                bm = bl + (br - bl) / 2;
                if (a[bm].vector_mul(r) > 0) bl = bm;
                else br = bm;
            }
            qr = bl;
        }
        if (ql <= qr) {
            pt v = r - l;
            ll tmp = rt.get_max(ql, qr, -v.y, v.x);
            ll C = v.vector_mul(l);
            cout << (tmp > C ? "Y" : "N") << "\n";
        } else {
            cout << "N\n";
        }
    }

    return 0;
}

• Subtask 1: 20 / 100