1081 - Square Queries
| Time Limit: 3 second(s) | Memory Limit: 64 MB |
Little Tommy is playing a game. The game is played on a 2D N x N grid. There is an integer in each cell of the grid. The rows and columns are numbered from 1 to N.
At first the board is shown. When the user presses a key, the screen shows three integers I, J, S which designates a square (I, J) to (I+S-1, J+S-1) in the grid. The player has to predict the largest integer found in this square. The user will be given points based on the difference between the actual result and the given result.
Tommy doesn't like to lose. So, he made a plan, he will take help of a computer to generate the result. But since he is not a good programmer, he is seeking your help.
Input
Input starts with an integer T (≤ 3), denoting the number of test cases.
The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 500), Q (0 ≤ Q ≤ 50000). Each of the next N lines will contain N space separated integers forming the grid. All the integers will be between 0 and 105.
Each of the next Q lines will contain a query which is in the form I J S (1 ≤ I, J ≤ N and 1 ≤ I + S, J + S < N and S > 0).
Output
For each test case, print the case number in a single line. Then for each query you have to print the maximum integer found in the square whose top left corner is (I, J) and whose bottom right corner is(I+S-1, J+S-1).
Sample Input | Output for Sample Input |
1
4 5
67 1 2 3
8 88 21 1
89 12 0 12
5 5 5 5
1 1 2
1 3 2
3 3 2
1 1 4
2 2 3
|
Case 1:
88
21
12
89
88
|
Note
Dataset is huge. Use faster i/o methods.
---------------------------------------------------EDITORIAL------------------------------------------------------
THIS PROBLEM CAN BE SOLVED USING DP OR SEGMENT TREE BUT DP SOLUTION WILL NOT PASS SINCE 500*500*500 MEMORY IS NOT ALLOWED ,
DP SOLUTION
#include<bits/stdc++.h>
using namespace std;
int dp[501][501][501];
int main()
{
int t;
cin>>t;
int cas=1;
while(t--)
{
memset(dp,0,sizeof dp);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&dp[i][j][1]);
}
for(int k=2;k<=501;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i+k-1<=n && j+k-1<=n)
{
int val1=max(dp[i][j][k-1],dp[i][j+1][k-1]);
int val2=max(dp[i+1][j][k-1],dp[i+1][j+1][k-1]);
dp[i][j][k]=max(val1,val2);
// cout<<" i "<<i<<" j "<<j<<" k "<<k<< dp[i][j][k]<<endl;
}
}
}
}
cout<<"Case "<<cas++<<": "<<endl;
for(int i=0;i<q;i++)
{
int a,b,c;
cin>>a>>b>>c; printf("%d \n",dp[a][b][c]);
}
}
return 0;
}
-----------------------------------------------seg tree approach ------------------------------------------
create seg tree for each row separately now for each query apply range max in rows including in that
row
------------------------------------------------code--------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
#define pf printf
#define S(x) scanf("%d", &x)
#define SL(x) scanf("%ld", &x)
#define out(C) printf("Case %d:\n", C);
#define FOR(i, x, y) for(int i=x; i<=y; i++)
#define MID(a,b) ((a+b)>>1)
#define mx 100010
template<class T>inline bool read(T &x) {
int c=getchar();
int sgn=1;
while(~c&&c<'0'||c>'9') {
if(c=='-')sgn=-1;
c=getchar();
}
for(x=0; ~c&&'0'<=c&&c<='9'; c=getchar())x=x*10+c-'0';
x*=sgn;
return ~c;
}
int grid[510][510];
int r,q;
int st[1700][1700];
void update (int tree[], int node, int l, int r, int x, int val){
// cout<<node<<" "<<l<<" "<<r<<" "<<x<<" "<<val<<endl;
if(l>x or r<x)return;
if(l==x and r==x){
tree[node]=val;
return;
}
int m=MID(l,r);
update(tree, node*2, l, m, x, val);
update(tree, node*2+1, m+1, r, x, val);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int tree[], int node, int l, int r, int x, int y){
if(l>=x and r<=y)
return tree[node];
int m = MID(l,r);
int ret=-1;
if(m>=x)
ret=query(tree,node*2, l, m, x, y);
if(m<y)
ret=max(ret, query(tree,node*2+1,m+1,r,x,y));
return ret;
}
int main() {
int test;
read(test);
FOR(C, 1, test) {
out(C);
read(r);read(q);
for(int i=1;i<=r;i++){
fill(st[i],st[i]+(r*3), -1);
for(int j=1;j<=r;j++){
read(grid[i][j]);
update(st[i],1,1,r,j,grid[i][j]);
}
}
// cout<<"ok"<<endl;
while(q--){
int x1,y1,y;
read(x1);read(y1);read(y);
int x2=x1+y-1,y2=y1+y-1;
int ans=-1;
for(int i=x1; i<=x2;i++){
ans = max(ans, query(st[i],1,1,r,y1,y2));
}
printf("%d\n",ans);
}
}
}
No comments:
Post a Comment