Submission #1208601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208601		vasfor	Tri (CEOI09_tri)	C++20	20 / 100	371 ms	100220 KiB

tri

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

const int inf = 1e9;
const ll inf64 = 1e18;

struct output {
    vector<int> res;

    void print() {
        for (auto x : res) cout << (x ? "Y" : "N") << "\n";
    }

    bool operator == (const output& o) const {
        return res == o.res;
    }
};

struct pt {
    ll x = 0;
    ll 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;
    }

    bool operator<(const pt& o) const {
        return vector_mul(o) > 0;
    }
};

pll intersect_lines(pt L1, pt L2) {
    // f(t) = x + t * y
    // x1 + t * y1 == x2 + t * y2
    // 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 __int128(p1.first) * p2.second < __int128(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;
        }
        pair<ll, bool> max_value = {0, false};
        for (int di = -1; di <= 1; ++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 (!max_value.second || max_value.first < tmp_value) {
                max_value = {tmp_value, true};
            }
        }

        // pair<ll, bool> max_value = {0, false};
        // for (auto z : st) {
        //     ll tmp_value = z.x * p + z.y * q;
        //     if (!max_value.second || max_value.first < tmp_value) {
        //         max_value = {tmp_value, true};
        //     }
        // }

        return max_value.first;
    }
};

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

    RangeTree(const vector<pt>& a): n(a.size()), A(a), pts(4 * n), 
        cht_xy_neg(4 * n), cht_yx_pos(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]));
            }
        }

        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]) 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_neg[v].get_max(-p, -q);
            else {
                if (q > 0) return cht_yx_pos[v].get_max(q, p);
            }
        } else {
            int tm = tl + (tr - tl) / 2;
            pair<ll, bool> res = {0, false};
            if (l <= tm) {
                ll tmp = get_max(v << 1, tl, tm, l, r, p, q);
                if (!res.second || res.first < tmp) res = {tmp, true};
            }
            if (r > tm) {
                ll tmp = get_max(v << 1 | 1, tm + 1, tr, l, r, p, q);
                if (!res.second || res.first < tmp) res = {tmp, true};
            }
            return res.first;
        }
    }

    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);
    }
};

struct input {
    int n, m;
    vector<pt> a;
    vector<pair<pt, pt>> b;

    input() = default;

    void read() {
        cin >> n >> m;
        a.resize(n);
        b.resize(m);
        for (auto& p : a) cin >> p.x >> p.y;
        for (auto& [l, r] : b) {
            cin >> l.x >> l.y >> r.x >> r.y;
        }
    }

    void print() {
        cout << n << " " << m << "\n";
        for (auto p : a) cout << p.x << " " << p.y << "\n";
        for (auto [l, r] : b) {
            cout << l.x << " " << l.y << " " << r.x << " " << r.y << "\n";
        }
    }

    void gen() {
        static mt19937 rnd(42);
        const int MAXN = 500;
        const int MAXX = 5;
        n = rnd() % MAXN + 1;
        m = rnd() % MAXN + 1;
        a.resize(n);
        for (auto& p : a) {
            p.x = rnd() % MAXX + 1;
            p.y = rnd() % MAXX + 1;
        }
        b.resize(m);
        for (auto& [l, r] : b) {
            while (1) {
                l.x = rnd() % (MAXX + 1);
                l.y = rnd() % (MAXX + 1);
                r.x = rnd() % (MAXX + 1);
                r.y = rnd() % (MAXX + 1);
                if (l.vector_mul(r) == 0) continue;
                if (l.x < r.x && l.y <= r.y) continue;
                if (l.x > r.x && l.y >= r.y) continue;
                int ok = 1;
                for (auto p : a) {
                    if (l.vector_mul(p) == 0 || r.vector_mul(p) == 0 || (r - l).vector_mul(p) == 0) {
                        ok = 0;
                        break;
                    }
                }
                if (!ok) continue;
                break;
            }
        }
    }

    void gen_max_test() {

    }

    output fast() {
        sort(a.begin(), a.end(), [&](pt p1, pt p2) {
            return p1.vector_mul(p2) > 0;
        });

        RangeTree rt(a);

        vector<int> res;
        res.reserve(m);

        for (auto [l, r] : b) {
            
            if (l.vector_mul(r) < 0) swap(l, r);
            int ql = 1e9, qr = -1e9;
            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) {
                int any = 0;
                pt v = r - l;
                ll C = v.vector_mul(l);
                ll tmp = rt.get_max(ql, qr, -v.y, v.x);
                res.push_back(tmp > C);
            } else {
                res.push_back(0);
            }
        }

        return output{res};
    }

// #ifdef DEBUG
    output slow() {
        vector<int> res;
        res.reserve(m);
        for (auto [l, r] : b) {
            if (l.vector_mul(r) < 0) swap(l, r);
            int any = 0;
            for (auto p : a) {
                if (l.vector_mul(p) > 0 && p.vector_mul(r) > 0 && (r - l).vector_mul(p - l) > 0) {
                    any = 1;
                    break;
                }
            }
            res.push_back(any);
        }
        return output{res};
    }
// #endif
};

void test_case() {
    input in;
    in.read();
    output res = in.fast();
    res.print();
}

void work() {
    int t = 1;
#ifdef DEBUG
    cin >> t;
#endif
    while (t--)
        test_case();
}

#ifdef DEBUG
void test() {
    for (int t = 1;;t++) {
        input in;
        in.gen();
        input in_fs = in;
        input in_sl = in;
        output fs = in_fs.fast();
        output sl = in_sl.slow();
        if (fs == sl) {
            cout << "OK" << endl;
            fs.print();
            cout << "\n=========" << endl;
        } else {
            cout << "WA " << t << "\n";
            cout << "exp\n";
            sl.print();
            cout << "\n=========\n";
            cout << "fnd\n";
            fs.print();
            cout << "\n=========\n";
            in.print();
            break;
        }
    }
}
#endif

#ifdef DEBUG
void max_test() {
    input in;
    in.gen_max_test();
    input in_fs = in;
    output fs = in_fs.fast();
    fs.print();
}
#endif

signed main() {

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

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

    work();
//    test();
//    max_test();

    return 0;
}

Compilation message (stderr)

tri.cpp: In member function 'll RangeTree::get_max(int, int, int, int, int, int, int)':
tri.cpp:175:5: warning: control reaches end of non-void function [-Wreturn-type]
  175 |     }
      |     ^

• Subtask 1: 20 / 100