Code: Select all
In the first line you will find N (0 <= N <= 500)
Code: Select all
5 5
Moderator: Board moderators
Code: Select all
In the first line you will find N (0 <= N <= 500)
Code: Select all
5 5
Robert Gerbicz wrote:From the problem statement:But in the first line of sample input I seeCode: Select all
In the first line you will find N (0 <= N <= 500)
Assuming that the problem desription is good I've got RTE for my program. It indicates that the description is wrong. It's really confusing, what is the second number in the first line? Is it the duplication of the N value, or what?!Code: Select all
5 5
Code: Select all
#include<stdio.h>
#include<string.h>
#include<math.h>
#define SZ 505
#define INF (1 << 30)
int mat[SZ][SZ] , n , ma[SZ][30] , mi[SZ][30] , m;
int main()
{
//freopen("c.in" , "rt" , stdin);
int i , j , k , l , q , a , b , c ,d;
char ch;
scanf("%d%d" , &n , &m);
for(i = 1;i<=n;i++)
for(j = 1;j<=25;j++)
{
ma[i][j] = 0;
mi[i][j] = INF;
}
k = (int) sqrt(m);
for(i = 1;i<=n;i++)
{
for(j = 1;j<=m;j++)
{
scanf("%d" , &mat[i][j]);
j % k == 0 ? l = j/k : l = (j/k)+1;
if(mat[i][j] > ma[i][l]) ma[i][l] = mat[i][j];
if(mat[i][j] < mi[i][l]) mi[i][l] = mat[i][j];
}
}
scanf("%d" , &q);
while(q--)
{
scanf(" %c" , &ch);
if(ch == 'c')
{
scanf("%d%d%d" , &a , &b , &c);
b % k == 0 ? l = b/k : l = (b/k)+1;
mat[a][b] = c;
if(ma[a][l] < c) ma[a][l] = c;
if(mi[a][l] > c) mi[a][l] = c;
}
else
{
scanf("%d%d%d%d" , &a , &b , &c , &d);
c > n ? c = n : c = c;
d > m ? d = m : d = d;
int mir , mar;
mar = 0;mir = INF;
for(i = a;i<=c;i++)
{
l = b;
while(l <= d)
{
if((l-1) % k == 0) break;
if(mar < mat[i][l])
mar = mat[i][l];
if(mir > mat[i][l])
mir = mat[i][l];
l++;
}
l = (l/k)+1;
for( ;l<= d/k;l++)
{
if(mar < ma[i][l])
mar = ma[i][l];
if(mir > mi[i][l])
mir = mi[i][l];
}
l = (d/k)*k+1;
for(;l<=d;l++)
{
if(mar < mat[i][l])
mar = mat[i][l];
if(mir > mat[i][l])
mir = mat[i][l];
}
}
printf("%d %d\n" , mar , mir);
}
}
return 0;
}
"x1 y1 x2 y2" which represent the coordinates of the upper left and lower right of where you must calculate the maximum and minimum change in population.
"x y v" indicating a change of the population of city C [x, y] by value v.
Which input format is right? There are or not characters 'c' and 'q'?q 1 1 2 3
c 2 3 10
q 1 1 5 5
q 1 2 2 2
Input:mmonish wrote:I got too many WA in this prob. here i post my code. Anyone please help me..
// CODE
Code: Select all
10 10
3 9 380 28471 29141 12245 0 5957 57 8535
5 9582 224 8649 2763 7 63 42 4462 0
11616 0 4647 4099 5 11 30991 0 32585 1
7 0 16 0 363 0 0 10947 1 31210
0 13 48 5997 8734 325 424 0 5949 18088
146 0 7 664 9175 22785 2055 4433 5783 586
214 31 363 8852 89 0 1748 9217 14348 21473
177 19922 0 2 973 73 27593 15329 71 7
0 2311 16 481 476 646 5081 80 66 36
234 22716 161 1 467 2594 8256 0 18567 0
10
c 7 4 2671
q 8 1 10 3
q 1 3 3 4
c 9 10 6454
c 10 6 1118
c 2 3 5946
c 8 9 3405
q 2 2 10 8
q 1 1 495 493
q 3 5 10 10
Code: Select all
22716 0
28471 224
30991 0
32585 0
32585 0
I agree. Actually for many problems for this contest, the example is too trivial and it doesn't really help much. And I find some of the problem statement simply doesn't make sense.anikov wrote:This is a very nice problem, but the problem description is one of the worst I have seen.
And this example is VERY stupid, not showing anything useful.
My n intervals work like this.O(log(n)) time for 'c' query
O(n*log(n)) time for 'q' query
I know, however i would code it whole night It's enoght for me to have n interval trees, if they pass TL.2d interval tree works here.
Each query and update is O((log n)^2)