fork download 
  1. #include <stdio.h>
  2.  
  3. #define MAX_N 100000
  4. #define CAMADAS 18
  5.  
  6. int main() {
  7.  
  8.     int n, q, k, p, t, contEventos, evento, totalPessoas, i, pessoas[CAMADAS][MAX_N];
  9.  
  10.     scanf("%d %d", &n, &q);
  11.  
  12.     for (i = 0; i < n; i++) {
  13.         scanf("%d", &pessoas[0][i]);
  14.     }
  15.     for (; i < MAX_N; i++) {
  16.         pessoas[0][i] = 0;
  17.     }
  18.     for (t = 1; t < CAMADAS; t++) {
  19.         for (i = 0; i < MAX_N / 2; i++) {
  20.             pessoas[t][i] = pessoas[t - 1][2 * i] + pessoas[t - 1][2 * i + 1];
  21.         }
  22.         for (; i < MAX_N; i++) {
  23.             pessoas[t][i] = 0;
  24.         }
  25.     }
  26.  
  27.     for (contEventos = 0; contEventos < q; contEventos++) {
  28.         scanf("%d", &evento);
  29.         scanf("%d", &k);
  30.  
  31.         if (evento == 0) {
  32.             scanf("%d", &p);
  33.             k--;
  34.             pessoas[0][k] = p;
  35.             for (t = 1; t < CAMADAS; t++) {
  36.                 pessoas[t][k / 2] = pessoas[t - 1][k] + pessoas[t - 1][k ^ 1];
  37.                 k /= 2;
  38.             }
  39.         } else if (evento == 1) {
  40.             totalPessoas = 0;
  41.  
  42.             for (t = 0; t < CAMADAS && k > 0; t++) {
  43.                 if (k & 1) totalPessoas += pessoas[t][k - 1];
  44.                 k /= 2;
  45.             }
  46.  
  47.             printf("%d\n", totalPessoas);
  48.         }
  49.  
  50.         // Para mostrar a tabela.
  51.         /*for (int y = 0; y < CAMADAS; y++) {
  52.             printf("\n|");
  53.             for (int z = 0; z < n; z++) {
  54.                 printf("%d ", pessoas[y][z]);
  55.             }
  56.             printf("|\n");
  57.         }*/
  58.     }
  59.  
  60.     return 0;
  61. }
Success #stdin #stdout 0s 8828KB
comments ()
stdin 
8 4
30 2 0 42 10 11 11 9
1 5
0 4 12
1 5
1 1
stdout 
84
54
30
https://ideone.com/kOnHgh
language:
C (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!