#P8042. 「COCI 2020.10」3D Histogram

    ID: 7135 传统题 2500ms 512MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>CF2800省选/NOI-分治算法前后缀最值同向双指针滑动窗口直线上包络双栈实现队列回滚维护状态二分查找COCI

「COCI 2020.10」3D Histogram

题目描述

给定一张三维的直方图,包含 nn 个接连排列的块。第 ii 个块有 11 米宽,aia_i 米高,bib_i 米长。换句话说,从前面看,就像是每组高度分别为 a1,a2,…,ana_1, a_2, \ldots , a_n 的直方图,从上面看,就像是每组高度分别为 b1,b2,…,bnb_1, b_2, \ldots , b_n 的直方图。

请求出三维直方图中能放下的最大体积的长方体。长方体的各个面需要和组成三维直方图的所有块的各个面平行。

输入格式

第一行一个正整数 nn。
接下来 nn 行,第 ii 行两个正整数 ai,bia_i,b_i,满足 1≤ai,bi≤1061\le a_i,b_i\le10^6。

输出格式

输出最大的体积的立方米数。由输入范围可知答案不超过 2×10172\times10^{17}。

5
5 3
4 4
2 1
3 2
1 5
24

下图显示了样例 1 的三维直方图。最大体积的长方体使用了前两个块的一部分,有 22 米宽,44 米高,33 米长。它的体积为 2⋅4⋅3=242 \cdot 4 \cdot 3 = 24 立方米。

6
3 1
2 1
2 2
2 3
1 1
2 2
8
5
15 19
5 6
1 13
3 7
1 2
285

数据范围与提示

子任务编号 分值 特殊限制
11 1818 1≤n≤20001 \le n \le 2000
22 8282 1≤n≤2×1051 \le n \le 2 \times {10}^5