URI Online Judge | 1112
Schweisen
By Leonardo Alt 
Brasil
Timelimit: 4 Brasil
Conan é um importante membro do Clube Atlético de Desrugenstein, que possui um time de futebol de campo profissional: ele é o responsável pelo gramado do campo onde ocorrem os jogos em casa. Em 2048 anos de história, o campo do CAD sempre esteve em perfeitas condições para os jogos, graças a Conan. Ele já ganhou vários prêmios por isso, sendo o mais importante deles o "Grama de Ouro", prêmio que ganhou 1024 vezes.
Amanhã acontecerá a final do campeonato Universal de futebol, e o CAD é um dos finalistas. Como o jogo será em casa, Conan foi ver o estado do gramado e reparar se necessário. Chegando lá, entrou em desespero ao ver várias schweisen no campo, estragando todo o gramado!!
Sendo assim, Conan precisa de sua ajuda para determinar quanto irá gastar com deswevileutssen para matar todas as schweisen. Cada deswevileutssen mata uma schwisen. Conan pode lhe mandar mensagens de dois tipos: dizendo que encontrou algumas schweisen, ou perguntando quanto ele vai gastar para matar certas schweisen.
Entrada
A entrada possui vários casos de teste. A primeira linha de um caso de teste contém 3 inteiros X (≤ 1000), Y (≤ 1000) e P (≤ 10), que representam, respectivamente, o tamanho (X e Y) do campo e o preço de cada deswevileutssen. A próxima linha contém um inteiro Q (≤ 10000). As próximas Q linhas representam mensagens de Conan para você, e estão em uma das duas seguintes formas:
- A N X Y - “Achei N (≤ 10) schweisen em (X,Y) - (0 ≤ X < Largura), (0 ≤ Y < Altura)”
- P X Y Z W - “Quanto vou gastar para matar todas as schweisen na área retangular de (X,Y) até (Z,W)?”
Considere que no início nenhuma schweisen foi vista.
A entrada termina quando X, Y e P são iguais a 0.
Saída
Para cada mensagem do tipo "P", imprima o valor que responde a pergunta feita. Deixe uma linha em branco após cada caso de teste, inclusive após o último.
#include <cstdio>
#include <algorithm>
#define MAXN 1010
#define LSOne(S) (S & (-S))
#define gc getchar_unlocked
void getint(int &x){
register int c = gc();
x = 0;
for(;(c<48 || c>57);c = gc());
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
using namespace std;
int bit[MAXN][MAXN];
void update(int x, int y, int val){
while(x < MAXN){
int ty = y;
while(ty < MAXN){
bit[x][ty] += val;
ty += LSOne(ty);
}
x += LSOne(x);
}
}
int sum(int x, int y){
if (x <= 0 || y <= 0) return 0;
int answer = 0;
while(x > 0){
int ty = y;
while(ty > 0){
answer += bit[x][ty];
ty -= LSOne(ty);
}
x -= LSOne(x);
}
return answer;
}
int query(int x1,int y1, int x2, int y2){
return sum(x2,y2) + sum(x1-1,y1-1) - sum(x1-1,y2) - sum(x2,y1-1);
}
int main(){
int x,y,z;
while(1){
getint(x);
getint(y);
getint(z);
if (x == 0 && y == 0 && z == 0) break;
for(int i=0;i<=x+1;i++){
for(int j=0;j<=y+1;j++){
bit[i][j] = 0;
}
}
int q;
getint(q);
while(q--){
char op;
scanf("%c",&op);
if (op == 'A'){
int a,b,c;
getint(a);
getint(b);
getint(c);
b++;
c++;
update(b,c,a);
}
if (op == 'P'){
int a,b,c,d;
getint(a);
getint(b);
getint(c);
getint(d);
if (a > c) swap(a,c);
if (b > d) swap(b,d);
printf("%d\n",z*query(a+1,b+1,c+1,d+1));
}
}
printf("\n");
}
return 0;
}
0 Comentários