Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1460
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1460
Grapevine
BrazilTimelimit: 3
In Quadradonia, all rural properties are square, all have the same area, all are perfectly flat and all have the sides aligned to the North-South and West-East axes.
Since properties are flat, the hills in Quadradonia look like a series of huge stairs' steps, with different heights. In a certain mountain, an interesting situation occurs in a rectangular area of N x M properties. Starting from anywhere within the region, traversing it in the West to East direction, the properties have non-descending heights. Similarly, traversing that region in the North to South direction, starting from anywhere, the properties have also non-descending heights.
A large wine company in Quadradonia wants to rent some properties from that region to grow wine grapes. The company is interested in some special varieties of wine grapes, which are productive only if grown in properties whose heights are within a certain interval. That is, the company is interested in renting properties whose heights are equal to or higher than a given altitude L, and equal to or lower than a given altitude U. To make it easier for harvesting, the rented properties must form a contiguous area. And since everyone in Quadradonia likes squares, the area to be rented must have the shape of a square.
The company has not yet decided which variety of grapes it will grow, and therefore it has a list of queries involving intervals, one for each grape variety. The figure below shows an area of interest of dimensions 4 x 5 (in number of properties) with examples of areas the company could rent to grow grapes in heights within the intervals given in the picture.
You must write a program that, given the description of the rectangular area of interest in the mountain, and a list of queries containing height intervals, determines, for each query, the largest side, in number of properties, of a contiguous square area with heights within the specified interval.
Input
The input contains several test cases. The first line of a test case contains two integers N and M, separated by a single space, representing respectively the number of properties in the North-South direction (1 ≤ N ≤ 500) and the number of properties in the West-East direction (1 ≤ M ≤ 500) of the region of interest. Each of the next N lines contains M integers Hi, j, separated by single spaces, indicating the heights of the properties in the region of interest ( 0 ≤ Hi, j ≤ 105, for 1 ≤ i ≤ N and 1 ≤ j ≤ M; also, Hi-1, j ≤ Hi, j and Hi, j-1 ≤ Hi, j). The next line contains an integer Q indicating the number of queries (1 ≤ Q ≤ 104). Each of the next Q lines describes a query, and contains two integers L and U, separated by a single space, indicating one interval of heights (0 ≤ L ≤ U ≤ 105). The heights of properties to be rented must be greater than or equal to L and less than or equal to U.
The last test case is followed by a line containing two zeros separated by a single space.
Output
For each test case in the input your program must print Q + 1 lines. Each of the first Q lines must contain a single integer, indicating the largest side, in number of properties, of a contiguous square area with heights within the interval specified in the respective input query. The last line to be printed for each test case is used as a separator and must contain a single character '-' (known as hyphen or minus sign).
| Sample Input | Sample Output |
|
4 5 |
3 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <deque>
#include <vector>
#define MP make_pair
using namespace std;
typedef pair < int, int> ii;
const int MAXN = 500;
vector<int> matriz[MAXN];
int n, m, q, maior[MAXN], menor[MAXN];
int func(int k) {
deque < ii> janela_maior, janela_menor;
for (int i = 0; i < k; i++) {
ii davez_maior = MP(i, maior[i]);
ii davez_menor = MP(i, menor[i]);
while (!janela_maior.empty() &&
janela_maior.back().second < = davez_maior.second)
janela_maior.pop_back();
janela_maior.push_back(davez_maior);
while (!janela_menor.empty() &&
janela_menor.back().second >= davez_menor.second)
janela_menor.pop_back();
janela_menor.push_back(davez_menor);
}
int delta = janela_menor.front().second - janela_maior.front().second + 1;
if (delta >= k) return 1;
for (int i = k; i < n; i++) {
ii davez_maior = MP(i, maior[i]);
ii davez_menor = MP(i, menor[i]);
while (!janela_maior.empty() &&
janela_maior.back().second < = davez_maior.second)
janela_maior.pop_back();
janela_maior.push_back(davez_maior);
if (janela_maior.front().first < = i - k) janela_maior.pop_front();
while (!janela_menor.empty() &&
janela_menor.back().second >= davez_menor.second)
janela_menor.pop_back();
janela_menor.push_back(davez_menor);
if (janela_menor.front().first < = i - k) janela_menor.pop_front();
delta = janela_menor.front().second - janela_maior.front().second + 1;
if (delta >= k) return 1;
}
return 0;
}
int main() {
while (scanf("%d %d", &n, &m) && (n || m)) {
for (int i = 0; i < n; i++) {
matriz[i].assign(m, 0);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &matriz[i][j]);
}
}
scanf("%d", &q);
while (q--) {
int a, b;
scanf("%d %d", &a, &b);
for (int i = 0; i < n; i++) {
if (matriz[i][m - 1] < a) {
maior[i] = m + 2;
} else {
vector<int>::iterator it1 =
lower_bound(matriz[i].begin(), matriz[i].end(), a);
maior[i] = it1 - matriz[i].begin() + 1;
}
if (matriz[i][0] > b) {
menor[i] = -1;
} else {
vector<int>::iterator it2 =
upper_bound(matriz[i].begin(), matriz[i].end(), b);
it2--;
menor[i] = it2 - matriz[i].begin() + 1;
}
// printf("%d: [%d,%d]\n",i,maior[i],menor[i]);
}
int ini = 1, fim = min(n, m), meio, resp = 0;
while (ini < = fim) {
meio = (ini + fim) / 2;
if (func(meio)) {
resp = meio;
ini = meio + 1;
} else
fim = meio - 1;
}
printf("%d\n", resp);
}
printf("-\n");
}
return 0;
}
Input
13 21 25 33 34
16 21 33 35 35
16 33 33 45 50
23 51 66 83 93
3
22 90
33 35
20 100
4 4
1 7 9 11
5 8 10 12
7 10 15 17
11 19 30 41
4
6 20
7 9
10 10
13 14
0 0
Output
2
4
-
3
1
1
0
-