#P1245. [Croatia2005]polja

    ID: 255 传统题 1000ms 512MiB 尝试: 11 已通过: 4 难度: 6 上传者: 标签>CF1900普及+/提高-离散化直方图最大矩形单调栈添加哨兵

[Croatia2005]polja

题目描述

Mickey 坐在已经升空的飞机上俯瞰大地,他发现土地被分成了很多个不同的矩形状,且由于覆盖的植被不同而显出不同的颜色。

Mickey 想寻找一个最大的矩形,它里面只显出一种颜色。在以下几张图中你可以看见样例中的几幅图,其中最终的答案区域已经被标记了出来。

请你编写一个程序计算一下所能看到的这样的矩形的面积,当然你可以放心,没有任何两块会互相重叠,然而二个矩形之间允许有共同点或公共边。

输入格式

输入文件的第一行将包含一个数字 N(1≤N≤2500)N(1 ≤ N ≤ 2500),它代表着土地上一共有 NN 个矩形块。

接下来的 NN 行中,每行都将有 55 个整数,依次记作X1,Y1,X2,Y2X_1,Y_1,X_2,Y_2 和 CC,其中 X1<X2,Y1<Y2X_1<X_2,Y_1<Y_2。 这些数字描绘了由 (X1,Y1),(X2,Y2)(X_1,Y_1),(X_2,Y_2) 围成的这样一个矩形块里显示出了颜色 C(1≤C≤100)C(1 ≤ C ≤ 100)。

我们保证 X1,Y1,X2,Y2X_1,Y_1,X_2,Y_2 的值都在 00 到 10910^9 之间(包含 00 和 10910^9)。

输出格式

输出文件应该只有一行,请输出如上题描述中的最大的矩形的面积。

注意得出的答案数据范围在 6464 位整型数以内,也就是 Pascal\text{Pascal} 的 int64,C/C++\text{C/C++} 的 long long\text{long long} 以内。

5 
1 1 3 3 1 
3 1 5 3 1 
1 4 3 6 1 
3 4 5 6 1 
0 3 6 4 2
8