QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#372520#3025. AssimilationSolitaryDream#TL 0ms0kbC++173.8kb2024-03-31 14:40:342024-03-31 14:40:36

Judging History

你现在查看的是最新测评结果

  • [2024-03-31 14:40:36]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-03-31 14:40:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
typedef pair<double, double> pdd;
pdd operator+(pdd a, pdd b) {
    return pdd(a.first + b.first, a.second + b.second);
}
struct Line {
    double k, c;
};
struct Convex {
    vector<Line> line;
    vector<double> cross;
    void Push(double k, double c) {
        line.push_back({k, c});
    }
    inline double CrossX(Line a, Line b) {
        return -(a.c - b.c) / (a.k - b.k); 
    }
    void Solve(vector<double> &sp) {
        sort(line.begin(), line.end(), [](Line a, Line b) {
            if (a.k == b.k) return a.c > b.c;
            return a.k > b.k;
        });
        int top = 0;
        for (int i = 1; i < line.size(); ++i) {
            while (top >= 0) {
                if (line[i].k == line[top].k) {
                    --top;
                } else if (top >= 1 && CrossX(line[i], line[top - 1]) <= CrossX(line[top], line[top - 1])) {
                    --top;
                } else break;
            }
            line[++top] = line[i];
        }
        line.resize(top + 1);
        cross.resize(line.size() - 1);
        for (int i = 0; i < cross.size(); ++i) cross[i] = CrossX(line[i], line[i + 1]);
    }
    pdd Get(double x) {
        int p = lower_bound(cross.begin(), cross.end(), x) - cross.begin();
        return {line[p].k, line[p].c};
    }
    void Clear() {
        line.clear();
        cross.clear();
    }
} U, D, R, L;
vector<pair<double, double>> A;
namespace Seg {
    double f[N];
    int D;
    inline void Init() {
        D = A.size() + 2;
        for (int i = 0; i < A.size(); ++i) {
            f[D + i] = A[i].second;
        }
        for (int i = D - 1; i; --i) f[i] = max(f[i << 1], f[i << 1 | 1]);
    }
    inline double Ask(int x, int y) {
        double ans = 0;
        for (int l = N + x - 1, r = N + y + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (~l & 1) ans = max(ans, f[l ^ 1]);
            if ( r & 1) ans = max(ans, f[r ^ 1]);
        }
        return ans;
    }
}
inline double GetArea(double x) {
    auto [k1, c1] = U.Get(x) + D.Get(x);
    auto [k2, c2] = R.Get(x) + L.Get(x);
    return (k1 * x + c1) * (k2 * x + c2);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(15);
    int Case;
    cin >> Case;
    while (Case--) {
        L.Clear(); R.Clear();
        U.Clear(); D.Clear();
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            int x, y, u, v, dx, dy;
            cin >> x >> y >> u >> v >> dx >> dy;
            U.Push(dy, v); D.Push(-dy, -y);
            R.Push(dx, u); L.Push(-dx, -x); 
        }
        vector<double> sp;
        U.Solve(sp); D.Solve(sp);
        R.Solve(sp); L.Solve(sp);
        for (int i = 0; i < n; ++i) 
        sort(sp.begin(), sp.end());
        sp.erase(unique(sp.begin(), sp.end()), sp.end());
        double last = 0;
        A.clear();
        A.push_back({0, GetArea(0)});
        for (auto cur : sp) {
            double mid = (last + cur) * 0.5;
            auto [k1, c1] = U.Get(mid) + D.Get(mid);
            auto [k2, c2] = R.Get(mid) + L.Get(mid);
            if (k1 * k2 < 0) {
                double x = -(k1 + k2) / (k1 * k2);
                if (x >= last && x <= cur) A.push_back({x, GetArea(x)});
            }
            A.push_back({cur, GetArea(cur)});
        }
        Seg::Init();
        int m;
        cin >> m;
        for (int i = 1; i <= m; ++i) {
            double x, y;
            cin >> x >> y;
            double ans = max(GetArea(x), GetArea(y));
            int p1 = lower_bound(A.begin(), A.end(), pdd(x, 0)) - A.begin();
            int p2 = lower_bound(A.begin(), A.end(), pdd(y, 0)) - A.begin() - 1;
            ans = max(ans, Seg::Ask(p1, p2));
            cout << ans << '\n';
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

29
9 1
1 1 2 1 1 1 1 1 1
4 1
3 2 1 1
5 316660370
269357435 105688553 346785866 295093544 181703417
6 43402885
39947441 27068237 43810814 44913378 40095941 34779892
22 319594
3815194 3056481 6593888 7315914 6593888 4794774 2561877 5256242 4920603 5256242 3606645 864746 1594265 1235578 2361430 2277526...

output:

705096198511282342017825511571456.000000000000000
12104194479543555470845405548249088.000000000000000
11583562611393181188504076922388480.000000000000000
13433201433907587800813401433702400.000000000000000
11691113521781205716576204669059072.000000000000000
11691113521781205716576204669059072.000000...

result: