#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <cstring>//used for memset
using namespace std;
long long int max( long long int a, long long int b) {
return ( a> b) ? a: b;
}
long long int leftto[ 100005 ] , rightto[ 100005 ] , width[ 100005 ] , matrix[ 1005 ] [ 1005 ] , solution[ 1005 ] [ 1005 ] ;
void compute_sol( long long int row, int m) {
long long int i;
stack< long long int > s;
for ( i= 0 ; i< m; i++ ) {
leftto[ i] = 0 ;
rightto[ i] = 0 ;
}
long long int temp; //to store indexes
//calculating leftto boundaries for each of the bar
for ( i= 0 ; i< m; i++ ) {
while ( ! s.empty ( ) ) {
//case when stack is not empty
if ( matrix[ row] [ s.top ( ) ] >= matrix[ row] [ i] ) {
//if the incoming element is less than the top of the stack
s.pop ( ) ;
}
else {
break ;
//incoming element is more
}
}
if ( s.empty ( ) ) {
temp = 0 ;
}
else {
temp = s.top ( ) + 1 ;
}
leftto[ i] = i - temp;
s.push ( i) ;
}
//empty the stack to store the rightto indexes
while ( ! s.empty ( ) ) {
s.pop ( ) ;
}
//calculating rightto boundaries for each of the bar
for ( i= m- 1 ; i>= 0 ; i-- ) {
while ( ! s.empty ( ) ) {
//case when stack is not empty
if ( matrix[ row] [ s.top ( ) ] >= matrix[ row] [ i] ) {
//if the incoming element is less than the top of the stack
s.pop ( ) ;
}
else {
break ;
//incoming element is more
}
}
if ( s.empty ( ) ) {
temp = m- 1 ;
}
else {
temp = s.top ( ) - 1 ;
}
rightto[ i] = temp- i;
s.push ( i) ;
}
//empty the stack to store the rightto indexes
while ( ! s.empty ( ) ) {
s.pop ( ) ;
}
//finding maximum width for each of the height present
memset ( width, 0 , sizeof ( width) ) ;
for ( i= 0 ; i< m; i++ ) {
width[ matrix[ row] [ i] ] = max( width[ matrix[ row] [ i] ] , leftto[ i] + rightto[ i] + 1 ) ;
//at row = 0, we can have an height of 0 or 1
//at row = 1, we can have an height of 0 or 1 or 2
}
long long int length = 0 ;
for ( i= 0 ; i<= row; i++ ) {
length = max( length, width[ row+ 1 - i] ) ;
//length of significant width height will be considered
//height of o widths are not considered
solution[ row] [ i] = length * ( row+ 1 - i) ;
//at one row if we are checking width[i]
//then in the row above it width[i-1] will be satisfied
//multiplication of row diff which will give us the result
}
for ( i= row; i>= 0 ; i-- ) {
solution[ row] [ i] = max( solution[ row] [ i] , solution[ row- 1 ] [ i] ) ;
solution[ row] [ i] = max( solution[ row] [ i] , solution[ row] [ i+ 1 ] ) ;
}
}
int main( ) {
long long int n, m, k, i, j;
scanf ( "%llu %llu %llu" , & n, & m, & k) ;
for ( i= 0 ; i< n; i++ ) {
for ( j= 0 ; j< m; j++ ) {
matrix[ i] [ j] = 0 ;
solution[ i] [ j] = 0 ;
}
}
for ( i= 0 ; i< k; i++ ) {
int x, y;
scanf ( "%d %d" , & x, & y) ;
matrix[ x- 1 ] [ y- 1 ] = 1 ;
//filling in the points where cant be built
}
//calculating histogram from the zero and 1 values in the matrix
for ( i= 0 ; i< m; i++ ) {
if ( matrix[ i] [ j] == 0 ) {
matrix[ i] [ j] = 1 ;
}
else {
matrix[ i] [ j] = 0 ;
}
}
for ( i= 1 ; i< n; i++ ) {
for ( j= 0 ; j< m; j++ ) {
if ( matrix[ i] [ j] == 1 ) {
matrix[ i] [ j] = 0 ;
}
else {
matrix[ i] [ j] + = matrix[ i- 1 ] [ j] + 1 ;
}
}
}
//till now we have created a multidimensional histogram
for ( i= 0 ; i< n; i++ ) {
compute_sol( i, m) ; //passing the row histogram on which operation needs to be done
}
int queries;
scanf ( "%d" , & queries) ;
for ( i= 0 ; i< n; i++ ) {
for ( j= 0 ; j< m; j++ ) {
printf ( "%llu " , solution[ i] [ j] ) ;
}
printf ( "\n " ) ;
}
while ( queries) {
int low, high;
scanf ( "%d %d" , & low, & high) ;
printf ( "%llu\n " , solution[ high- 1 ] [ low- 1 ] ) ;
queries-- ;
}
return 0 ;
}
CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8Y3N0cmluZz4vL3VzZWQgZm9yIG1lbXNldAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmxvbmcgbG9uZyBpbnQgbWF4KGxvbmcgbG9uZyBpbnQgYSwgbG9uZyBsb25nIGludCBiKXsKCiAgcmV0dXJuIChhPmIpP2E6YjsKCn0KCmxvbmcgbG9uZyBpbnQgbGVmdHRvWzEwMDAwNV0sIHJpZ2h0dG9bMTAwMDA1XSwgd2lkdGhbMTAwMDA1XSwgbWF0cml4WzEwMDVdWzEwMDVdLCBzb2x1dGlvblsxMDA1XVsxMDA1XTsKCnZvaWQgY29tcHV0ZV9zb2wobG9uZyBsb25nIGludCByb3csIGludCBtKXsKCQogICAgbG9uZyBsb25nIGludCBpOwoJICBzdGFjazxsb25nIGxvbmcgaW50PiBzOwoKICAgIGZvcihpPTA7aTxtO2krKyl7CiAgICAJbGVmdHRvW2ldID0gMDsKICAgIAlyaWdodHRvW2ldID0gMDsKICAJfQoKICAJbG9uZyBsb25nIGludCB0ZW1wOy8vdG8gc3RvcmUgaW5kZXhlcwoKICAJLy9jYWxjdWxhdGluZyBsZWZ0dG8gYm91bmRhcmllcyBmb3IgZWFjaCBvZiB0aGUgYmFyCiAgCWZvcihpPTA7aTxtO2krKyl7CgogICAgCXdoaWxlKCFzLmVtcHR5KCkpewogICAgICAJCS8vY2FzZSB3aGVuIHN0YWNrIGlzIG5vdCBlbXB0eQogICAgICAJCWlmKG1hdHJpeFtyb3ddW3MudG9wKCldPj1tYXRyaXhbcm93XVtpXSl7CiAgICAgICAgCS8vaWYgdGhlIGluY29taW5nIGVsZW1lbnQgaXMgbGVzcyB0aGFuIHRoZSB0b3Agb2YgdGhlIHN0YWNrCiAgICAgICAgCQlzLnBvcCgpOwogICAgICAJCX0KICAgICAgCQllbHNlewogICAgICAgIAkJYnJlYWs7CiAgICAgICAgCQkvL2luY29taW5nIGVsZW1lbnQgaXMgbW9yZQogICAgICAJICAgCX0KICAgIAl9CgogICAgCWlmKHMuZW1wdHkoKSl7CiAgICAJCXRlbXAgPSAwOwogICAgCX0KICAgIAllbHNlewogICAgCQl0ZW1wID0gcy50b3AoKSsxOwogICAgCX0KCiAgICAJbGVmdHRvW2ldID0gaSAtIHRlbXA7CiAgICAJcy5wdXNoKGkpOwogICAgCQoJfQoJLy9lbXB0eSB0aGUgc3RhY2sgdG8gc3RvcmUgdGhlIHJpZ2h0dG8gaW5kZXhlcwoKCXdoaWxlKCFzLmVtcHR5KCkpewoJCXMucG9wKCk7Cgl9CgoJLy9jYWxjdWxhdGluZyByaWdodHRvIGJvdW5kYXJpZXMgZm9yIGVhY2ggb2YgdGhlIGJhcgogIAlmb3IoaT1tLTE7aT49MDtpLS0pewoKICAgIAl3aGlsZSghcy5lbXB0eSgpKXsKICAgICAgCQkvL2Nhc2Ugd2hlbiBzdGFjayBpcyBub3QgZW1wdHkKICAgICAgCQlpZihtYXRyaXhbcm93XVtzLnRvcCgpXT49bWF0cml4W3Jvd11baV0pewogICAgICAgIAkvL2lmIHRoZSBpbmNvbWluZyBlbGVtZW50IGlzIGxlc3MgdGhhbiB0aGUgdG9wIG9mIHRoZSBzdGFjawogICAgICAgIAkJcy5wb3AoKTsKICAgICAgCQl9CiAgICAgIAkJZWxzZXsKICAgICAgICAJCWJyZWFrOwogICAgICAgIAkJLy9pbmNvbWluZyBlbGVtZW50IGlzIG1vcmUKICAgICAgCSAgIAl9CiAgICAJfQoKICAgIAlpZihzLmVtcHR5KCkpewogICAgCQl0ZW1wID0gbS0xOwogICAgCX0KICAgIAllbHNlewogICAgCQl0ZW1wID0gcy50b3AoKS0xOwogICAgCX0KCiAgICAJcmlnaHR0b1tpXSA9IHRlbXAtaTsKICAgIAlzLnB1c2goaSk7CgoJfQoJLy9lbXB0eSB0aGUgc3RhY2sgdG8gc3RvcmUgdGhlIHJpZ2h0dG8gaW5kZXhlcwoKCXdoaWxlKCFzLmVtcHR5KCkpewoJCXMucG9wKCk7Cgl9CgoJLy9maW5kaW5nIG1heGltdW0gd2lkdGggZm9yIGVhY2ggb2YgdGhlIGhlaWdodCBwcmVzZW50CgltZW1zZXQod2lkdGgsIDAsIHNpemVvZih3aWR0aCkpOwoKICBmb3IoaT0wO2k8bTtpKyspewogICAgd2lkdGhbbWF0cml4W3Jvd11baV1dID0gbWF4KHdpZHRoW21hdHJpeFtyb3ddW2ldXSwgbGVmdHRvW2ldK3JpZ2h0dG9baV0rMSk7CiAgICAvL2F0IHJvdyA9IDAsIHdlIGNhbiBoYXZlIGFuIGhlaWdodCBvZiAwIG9yIDEKICAgIC8vYXQgcm93ID0gMSwgd2UgY2FuIGhhdmUgYW4gaGVpZ2h0IG9mIDAgb3IgMSBvciAyCiAgfQoKICBsb25nIGxvbmcgaW50IGxlbmd0aCA9IDA7CgogIGZvcihpPTA7aTw9cm93O2krKyl7CiAgICBsZW5ndGggPSBtYXgobGVuZ3RoLCB3aWR0aFtyb3crMS1pXSk7CiAgICAvL2xlbmd0aCBvZiBzaWduaWZpY2FudCB3aWR0aCBoZWlnaHQgd2lsbCBiZSBjb25zaWRlcmVkCiAgICAvL2hlaWdodCBvZiBvIHdpZHRocyBhcmUgbm90IGNvbnNpZGVyZWQKICAgIHNvbHV0aW9uW3Jvd11baV0gPSBsZW5ndGggKiAocm93KzEtaSk7CiAgICAvL2F0IG9uZSByb3cgaWYgd2UgYXJlIGNoZWNraW5nIHdpZHRoW2ldCiAgICAvL3RoZW4gaW4gdGhlIHJvdyBhYm92ZSBpdCB3aWR0aFtpLTFdIHdpbGwgYmUgc2F0aXNmaWVkIAogICAgLy9tdWx0aXBsaWNhdGlvbiBvZiByb3cgZGlmZiB3aGljaCB3aWxsIGdpdmUgdXMgdGhlIHJlc3VsdAogIH0KCiAgZm9yKGk9cm93O2k+PTA7aS0tKXsKCiAgICBzb2x1dGlvbltyb3ddW2ldID0gbWF4KHNvbHV0aW9uW3Jvd11baV0sIHNvbHV0aW9uW3Jvdy0xXVtpXSk7CiAgICBzb2x1dGlvbltyb3ddW2ldID0gbWF4KHNvbHV0aW9uW3Jvd11baV0sIHNvbHV0aW9uW3Jvd11baSsxXSk7CiAgfQoKfQoKaW50IG1haW4oKXsKCglsb25nIGxvbmcgaW50IG4sIG0sIGssIGksIGo7CgogIHNjYW5mKCIlbGx1ICVsbHUgJWxsdSIsICZuLCAmbSwgJmspOwoKICBmb3IoaT0wO2k8bjtpKyspewogICAgZm9yKGo9MDtqPG07aisrKXsKICAgICAgbWF0cml4W2ldW2pdID0gMDsKICAgICAgc29sdXRpb25baV1bal0gPSAwOwogICAgfQogIH0KCiAgZm9yKGk9MDtpPGs7aSsrKXsKCiAgICBpbnQgeCwgeTsKICAgIHNjYW5mKCIlZCAlZCIsICZ4LCAmeSk7CiAgICBtYXRyaXhbeC0xXVt5LTFdID0gMTsKICAgIC8vZmlsbGluZyBpbiB0aGUgcG9pbnRzIHdoZXJlIGNhbnQgYmUgYnVpbHQgCiAgfQoKICAvL2NhbGN1bGF0aW5nIGhpc3RvZ3JhbSBmcm9tIHRoZSB6ZXJvIGFuZCAxIHZhbHVlcyBpbiB0aGUgbWF0cml4CiAgZm9yKGk9MDtpPG07aSsrKXsKICAgIGlmKG1hdHJpeFtpXVtqXT09MCl7CiAgICAgIG1hdHJpeFtpXVtqXSA9IDE7CiAgICB9CiAgICBlbHNlewogICAgICBtYXRyaXhbaV1bal0gPSAwOwogICAgfQogIH0KICBmb3IoaT0xO2k8bjtpKyspewogICAgZm9yKGo9MDtqPG07aisrKXsKICAgICAgaWYobWF0cml4W2ldW2pdPT0xKXsKICAgICAgICBtYXRyaXhbaV1bal0gPSAwOwogICAgICB9CiAgICAgIGVsc2V7CiAgICAgICAgbWF0cml4W2ldW2pdICs9IG1hdHJpeFtpLTFdW2pdICsgMTsKICAgICAgfQogICAgfQogIH0KICAvL3RpbGwgbm93IHdlIGhhdmUgY3JlYXRlZCBhIG11bHRpZGltZW5zaW9uYWwgaGlzdG9ncmFtCgogIGZvcihpPTA7aTxuO2krKyl7CiAgICBjb21wdXRlX3NvbChpLCBtKTsvL3Bhc3NpbmcgdGhlIHJvdyBoaXN0b2dyYW0gb24gd2hpY2ggb3BlcmF0aW9uIG5lZWRzIHRvIGJlIGRvbmUKICB9CgogIGludCBxdWVyaWVzOwogIHNjYW5mKCIlZCIsICZxdWVyaWVzKTsKCiAgZm9yKGk9MDtpPG47aSsrKXsKICAgIGZvcihqPTA7ajxtO2orKyl7CiAgICAgIHByaW50ZigiJWxsdSAiLCBzb2x1dGlvbltpXVtqXSk7CiAgICB9CiAgICBwcmludGYoIlxuIik7CiAgfQogIHdoaWxlKHF1ZXJpZXMpewoKICAgIGludCBsb3csIGhpZ2g7CiAgICBzY2FuZigiJWQgJWQiLCAmbG93LCAmaGlnaCk7CiAgICBwcmludGYoIiVsbHVcbiIsIHNvbHV0aW9uW2hpZ2gtMV1bbG93LTFdKTsKICAgIHF1ZXJpZXMtLTsKICB9CgogIHJldHVybiAwOwp9CgoK
compilation info
prog.cpp: In function 'int main()':
prog.cpp:127:37: error: 'scanf' was not declared in this scope
scanf("%llu %llu %llu", &n, &m, &k);
^
prog.cpp:174:37: error: 'printf' was not declared in this scope
printf("%llu ", solution[i][j]);
^
prog.cpp:176:16: error: 'printf' was not declared in this scope
printf("\n");
^
prog.cpp:182:45: error: 'printf' was not declared in this scope
printf("%llu\n", solution[high-1][low-1]);
^
stdout