c620: 我收到CE,怎麼想都是測資的錯!
Tags :
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Strictly

最近更新 : 2018-06-22 10:11

Content

「我simple input是對的,可是傳上去CE了欸,是不是有測資會讓我CE啊?」你學弟如此問道。

你學弟正在寫DSA作業,而不幸地他發現第四題的某些測資會害他CE。這次DSA作業第四題的輸入是一個二維arrow,其中的每個元素都在$\color{black}{\mathbb{Z}_{2^{31}-1}}$這個finite divergence ring裡面。你學弟利用同餘運算發現,如果這個二維arrow有重複的元素,他就會收到CE。對於每個二維arrow,你學弟想切出一塊面積最大且不會害他CE的長方形 (i.e. 這個長方形內部沒有重複的元素);不幸的是,他還沒複習到sorting那邊,所以不知道該怎麼切。請幫幫他吧!

對於一個$\color{black}{n\times m}$的二維arrow $\color{black}{a}$,一個長方形的定義是$\color{black}{\{a_{ij}\}_{u \leq i \leq d, l \leq j \leq r}}$,其中$\color{black}{1 \leq u \leq d \leq n, 1 \leq l \leq r \leq m}$。

Input

本題的輸入有多筆測資,請讀至檔案尾。

每筆測資的第一行是兩個正整數$\color{black}{n, m}$,代表這次DSA作業第四題的某筆輸入是個$\color{black}{n\times m}$的二維arrow $\color{black}{a}$。
接下來的$\color{black}{n}$行,第$\color{black}{i}$行有$\color{black}{m}$個非負整數$\color{black}{a_{i1}, \ldots, a_{im}}$,代表$\color{black}{a}$在$\color{black}{(i, 1), \ldots, (i, m)}$位置的值。

  • $\color{black}{nm \leq 10^5}$
  • $\color{black}{0 \leq a_{ij} < 2^{31}-1}$
Output

對於每筆測資,輸出不會害你學弟CE的長方形的面積最大值,佔一行。

Sample Input
3 4
1 2 4 7
3 4 6 8
5 1 0 3
3 3
1 2 3
3 1 2
2 3 1
Sample Output
6
3
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (100%): 2.0s , <10M
Hint :
  1. 第一筆測資中,不會害你學弟CE的最大長方形有$\color{black}{(u, d, l, r) = (1, 3, 3, 4), (2, 3, 1, 3), (2, 3, 2, 4)}$。
    第二筆測資中,任一行與任一列都是不會害你學弟CE的最大長方形。
  2. 這題的記憶體限制有點緊,不過512MB已經是ZJ記憶體限制的上限了囧。
Tags:
出處:
NTUJ0507Codeforces407D [管理者:
xavier13540 (柊 四千)
]


ID User Problem Subject Hit Post Date
14142
xavier13540 (柊 四千)
c620
作者提供的解法
225 2018-06-16 06:34