POJ 2019 Cornfields [二维RMQ]
Cornfields
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 7963 | Accepted: 3822 |
Description
FJ has, at great expense, surveyed his square farm of N x N hectares (1 <= N <= 250). Each hectare has an integer elevation (0 <= elevation <= 250) associated with it.
FJ will present your program with the elevations and a set of K (1 <= K <= 100,000) queries of the form "in this B x B submatrix, what is the maximum and minimum elevation?". The integer B (1 <= B <= N) is the size of one edge of the square cornfield and is a constant for every inquiry. Help FJ find the best place to put his cornfield.
Input
* Lines 2..N+1: Each line contains N space-separated integers. Line 2 represents row 1; line 3 represents row 2, etc. The first integer on each line represents column 1; the second integer represents column 2; etc.
* Lines N+2..N+K+1: Each line contains two space-separated integers representing a query. The first integer is the top row of the query; the second integer is the left column of the query. The integers are in the range 1..N-B+1.
Output
Sample Input
5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2
Sample Output
5
Source
分析:
二维$RMQ$模板题。
就是模板,但是卡空间是真恶心。。。卡了一个小时。
Code:
//It is made by HolseLee on 4th Sep 2018
//POJ 2019
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int N=;
int mi[N][N][][];
int ma[N][N][][]; void ready(int n)
{
for(int i=; (<<i)<=n; ++i)
for(int j=; (<<j)<=n; ++j) {
if( i== && j== ) continue;
for(int line=; line+(<<i)-<=n; ++line)
for(int ray=; ray+(<<j)-<=n; ++ray) {
if( i ) {
mi[line][ray][i][j]=min(mi[line][ray][i-][j],mi[line+(<<(i-))][ray][i-][j]);
ma[line][ray][i][j]=max(ma[line][ray][i-][j],ma[line+(<<(i-))][ray][i-][j]);
} else {
mi[line][ray][i][j]=min(mi[line][ray][i][j-],mi[line][ray+(<<(j-))][i][j-]);
ma[line][ray][i][j]=max(ma[line][ray][i][j-],ma[line][ray+(<<(j-))][i][j-]);
}
}
}
} int quary(int x,int y,int X,int Y)
{
int kx=,ky=,m1,m2,m3,m4,minn,maxx;
while( (<<(kx+))<=X-x+ ) kx++;
while( (<<(ky+))<=Y-y+ ) ky++; minn=min(min(mi[x][y][kx][ky],mi[X-(<<kx)+][Y-(<<ky)+][kx][ky]),min(mi[X-(<<kx)+][y][kx][ky],mi[x][Y-(<<ky)+][kx][ky])); maxx=max(max(ma[x][y][kx][ky],ma[X-(<<kx)+][Y-(<<ky)+][kx][ky]),max(ma[X-(<<kx)+][y][kx][ky],ma[x][Y-(<<ky)+][kx][ky])); return maxx-minn;
} int main()
{
int n,B,m;
while( scanf("%d%d%d",&n,&B,&m)== && n && B &&m ) {
int x,y;
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j) {
scanf("%d",&x);
mi[i][j][][]=ma[i][j][][]=x;
}
ready(n);
while( m-- ) {
scanf("%d%d",&x,&y);
int ans=quary(x,y,x+B-,y+B-);
printf("%d\n",ans);
}
}
return ;
}
最新文章
- Lae程序员小漫画(三),仅供一乐
- css:去掉手机浏览器上点击时的边框和阴影
- AppInventor学习笔记(五)&mdash;&mdash;瓢虫快跑应用学习
- Angularjs中编写指令模版
- 从一个标准 url 里取出文件的扩展名
- yum nfs
- 用CSS3写的钟表
- 雅虎工程师初始化css
- javascript数组、对象和Null的typeof同为object,区分解决办法
- scala PartialFunction
- CF1114D 【Flood Fill】
- java PDF添加图层,支持多页图层添加
- Annihilate(SA)
- Ncurses - Panel
- Oracle通过dblink连接MySQL
- Java压缩图片的实现类
- HDU3440(差分约束)
- Attr.checkId()方法
- 互斥量、条件变量与pthread_cond_wait()函数的使用,详解(一)
- Oracle Study之-AIX6.1构建Oracle 10gR2 RAC(3)
热门文章
- tf.train.batch的偶尔乱序问题
- 关于 Capella 需要纠正的语音
- (转)使用Excel批量给数据添加单引号和逗号
- LintCode 402: Continuous Subarray Sum
- [AHOI2012]树屋阶梯 题解(卡特兰数)
- 【洛谷 P4291】 [HAOI2008]排名系统(Splay,Trie)
- 【洛谷 P2900】 [USACO08MAR]土地征用Land Acquisition(斜率优化,单调栈)
- java反序列化漏洞
- 读书笔记 effective c++ Item 4 确保对象被使用前进行初始化
- JavaScript 跳转 页面