Untitled
unknown
plain_text
5 months ago
3.0 kB
3
Indexable
#include <bits/stdc++.h> using namespace std; #define ll long long int tt, tc; const int MAXA = 2e6 + 9; const int DELTA = 1e6; typedef long long ftype; typedef complex<ftype> point; #define x real #define y imag ftype dot(point a, point b) { return (conj(a) * b).x(); } ftype f(point a, ftype X) { return dot(a, {X, 1}); } point line[MAXA << 2]; vector<vector<tuple<int, point, point>>> st; void add_line(point nw, int v = 1, int l = 0, int r = MAXA - 5) { int m = (l + r) / 2; bool lef = f(nw, l - DELTA) > f(line[v], l - DELTA); bool mid = f(nw, m - DELTA) > f(line[v], m - DELTA); if(mid) { swap(line[v], nw); // line[v] = nw st.back().emplace_back(v, line[v], nw); } if(r - l == 1) { return; } else if(lef != mid) { add_line(nw, 2 * v, l, m); } else { add_line(nw, 2 * v + 1, m, r); } } void roll_back() { auto V = st.back(); st.pop_back(); reverse(V.begin(), V.end()); for (auto& [v, X, y] : V) { swap(line[v], X); } } ftype get(int X, int v = 1, int l = 0, int r = MAXA - 5) { int m = (l + r) / 2; if(r - l == 1) { return f(line[v], X); } else if(X < m) { return max(f(line[v], X), get(X, 2 * v, l, m)); } else { return max(f(line[v], X), get(X, 2 * v + 1, m, r)); } } void solve() { // add line (x, y) // query (p) : max_{x, y} (x * p + y) add_line(1, 2); add_line(5, 1); cout << get(1) << "\n"; // int n = 1; // int index = 0; // vector<vector<int>> g(n); // vector<ll> X(n), Y(n); // vector<pair<int, ll>> ask; // first is vertex, second is value // int q; // cin >> q; // while (q--) { // int type; // cin >> type; // if (type == 1) { // cin >> index; // } else if (type == 2) { // ll XX, YY; // cin >> XX >> YY; // int new_index; // cin >> new_index; // g[index].push_back(new_index); // X.push_back(XX); // Y.push_back(YY); // n++; // g.push_back(vector<int>()); // index = new_index; // } else { // ll V; // cin >> V; // ask.emplace_back(index, V); // } // } // vector<vector<int>> queries(n); // q = ask.size(); // vector<ll> query_ans(q); // for (int i = 0; i < q; i++) { // queries[ask[i].first].push_back(i); // } // function<void(int)> dfs = [&](int v) { // point nw(X[v], Y[v]); // st.push_back(vector<tuple<int, point, point>>()); // add_line(nw); // for (int query : queries[v]) query_ans[query] = get(ask[query].second); // for (int u : g[v]) dfs(u); // roll_back(); // }; // for (ll val : query_ans) cout << val << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); tt = 1, tc = 1; // cin >> tt; while (tt--) { solve(); tc++; } }
Editor is loading...
Leave a Comment