OMI 2011 Problema 3 ( La guardia negra)

OMI 2011 Problema 3 ( La guardia negra)

Problema:
La guardia negra
Según la canción del fuego y el hielo, la guardia de los centinelas negros ha defendido al reino de Westeros de las amenazas del norte durante los últimos 8,000 años. A últimas fechas un gran número de huestes enemigas se ha venido concentrando en la frontera norte de Westeros. El comandante de la guardia, Lord Snow, ha mandado llamar por ti para que le ayudes a planear la defensa.
La guardia tiene representado el campamento enemigo como una cuadrícula de M filas por N columnas, en cada casilla de la cuadrícula hay un número si,j que representa la cantidad de soldados enemigos en esa casilla.
La guardia cuenta con una catapulta capaz de lanzar un proyectil explosivo a cualquier lugar de esta cuadrícula. Al explotar, el proyectil eliminará a todos los soldados enemigos que se encuentren a una distancia menor o igual a un número di que depende del proyectil en cuestión. La distancia entre dos casillas se define como la suma del valor absoluto de la diferencia de sus columnas mas el valor absoluto de la diferencia de sus filas.
El comandante de la guardia quiere que desarrolles un programa para calcular la cantidad de soldados que eliminaría un proyectil específico si fuera lanzado en una cierta casilla.
Problema
Escribe un programa que dada la cuadrícula del campamento, el número de soldados en cada casilla, el número de proyectiles, la distancia de alcance de cada uno y el lugar donde quieres lanzarlo, calcule el número de enemigos que serán eliminados con cada proyectil.
Restricciones
1 <= M, N <= 1,000
1 <= P <= 100,000
0 <= si,j <= 1,000,000,000 0 <= di <= 500
Entrada
Filas y de columnas del campamento respectivamente. Número de proyectiles con los que cuenta la guardia. Número de soldados en la casilla (i,j).
Alcance del proyectil i.
Tu programa debe leer del teclado la siguiente información:
En la primer línea los números M y N que representan el número de filas y columnas.
 En cada una de las siguientes M líneas hay N números enteros separados por un
espacio que representan los soldados en cada casilla del campamento.
 En la siguiente línea el número P de proyectiles que tiene la guardia.
 En las últimas P líneas hay 3 enteros separados por espacios en cada una que
representan la fila y columna donde se lanzará un proyectil y la distancia de alcance del mismo.
Tanto las filas como las columnas inician nuieradas a partir del 0 y hasta M-1 y N-1 respectivamente. La fila 0 es la fila superior y la columna 0 es la columna hasta la izquierda.
Puedes estar seguro de que los proyectiles serán lanzados de tal forma que su alcance no exceda el campamento, es decir, ninguna explosión llegará a una casilla que este fuera de la cuadrícula.
Salida
Tu programa deberá escribir a la pantalla P líneas con un número cada una. La i-eȁsima línea debe contener la cantidad de enemigos que serían eliminados al lanzar el proyectil i.

Solucion:

El problema de la guardia negra es un problema que parece complicado, pero habría que tomarnos un tiempo para analizarlo, realmente uno debe responder a los querys que se solicitan, en la posición pos_fila, pos_columna, con diámetro T contar cuantos soldados son eliminados, bueno podemos tratar de encontrar una solución dinámica que cuente todo pero es muy costoso, mejor vamos a hacerlo a fuerza bruta. Si escucharon bien a fuerza bruta, pero bueno no lo hagamos tan bruta, solo respondamos a lo que nos preguntan, primero tenemos que observar que para una posición fil, col, con un diámetro T, siempre vamos a contar los rangos de para cada columna de la celda [fila – t, col ] hasta [fila + t, col], sacamos toda la suma, y luego para la coluina de atrás [fila – t + 1, col - 1] hasta [ fila + t – 1 , col – 1] y asi sucesivamente, mi propuesta de solución es precacular estas sumas, si en un arreglo de suma, tenemos la suma desde la base de la matriz que es [ fila = n – 1, col = ? ] , hasta la fila 0 [ fila = 0 , col = ?] , entonces para calcular toda la suma del rango que necesitamos cacular nos tomara una operación por ejemplo si quiero la suma de la celda[ 10, 4] a la celda[ 1000, 4 ] ( observen que la columna siempre es la misma) basta con sacar del arreglo suma[ 10, 4] – suma[ 1000 + 1 , 4] , ya que suma[10, 4], tiene la suma de todos los suma[ 10 , 4] , suma[ 10 , 5] + suma[10, 6] …. , y le restamos las suma que son suma[ 1001, 4] + suma[ 1002, 4] + suma[ 1003, 4] …..
Ya tenemos la suma ahora solo hay que sacar las T*2 + 1 columnas, como solo son 100,000 preguntas y a lo mas T es 1000, tenemos que en el peor de los casos se harán 100,000,000 operaciones que corre en menos de 1 segundo.
Veamos la implementación:

/*
   Autor: Rodrigo Burgos Dominguez
   Problema: La guardia negra
*/
# include "stdio.h"
# include "string.h"
int cnt[1001][1001];
long long sum[1002][1002];

int n, m;

long long get( int x, int y ){
  if( x < 0 || x >= n || y < 0 || y >= m ) return 0;
  return sum[x][y]; 
}

long long suma( int px, int py, int t){
    long long sum = 0;
    int x, y, d;
    for( x = py, d = 0; x >= 0 && x >= py - t ; x--, d++){
     sum += get( px - ( t - d ), x ) - get( px + ( t - d ) + 1, x);
    } 
    for( x = py + 1, d = 1 ; x < m && x <= py + t ; x++, d++){
     sum += get( px - ( t - d ), x ) - get( px + ( t - d ) + 1, x);
    } 
    return sum;
}

main(){
  int x, y, q, nq, px, py, t;
  scanf("%d %d", &n, &m);
  for( x = 0; x < n; x++)
   for( y = 0; y < m; y++) scanf("%d", &cnt[x][y]);
  
  for( x = n - 1; x >= 0; x--){
    for( y = 0; y < m; y++)
        sum[ x ][ y ] = sum[x + 1][ y ] + cnt[x][y];
  }
  scanf("%d", &nq);
  for( q = 0; q < nq; q++){
    scanf("%d %d %d", &px, &py, &t);
    printf("%lld\n", suma( px, py, t)); 
  }
  return 0; 
}