fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <cassert>
  5.  
  6. using namespace std;
  7.  
  8. /*
  9.  * A lógica do isleaf não é necessária pra uma segtree de soma
  10.  * (mas resolvi incluí-la pra mostrar como generalizar a técnica
  11.  * para uma segtree de máximo, por exemplo)
  12.  */
  13.  
  14. int tree[2*1024][2*1024];
  15. int roots[2][20], isleaf[2][20], sizes[2];
  16.  
  17. int xy, A, B, only_contained;
  18. void gen(int root, int st, int end) {
  19.     if(st > B || end < A) return;
  20.     if((st >= A && end <= B) || !only_contained) {
  21.         roots[xy][sizes[xy]] = root;
  22.         isleaf[xy][sizes[xy]++] = !(end-st);
  23.     }
  24.     if(st >= A && end <= B) return;
  25.  
  26.     int mid = (st+end)/2;
  27.     gen(2*root+1, st, mid);
  28.     gen(2*root+2, mid+1, end);
  29. }
  30.  
  31. int main() {
  32.     int s,ins;
  33.     while (1) {
  34.         scanf("%d", &ins);
  35.  
  36.         switch(ins) {
  37.         case 3:
  38.             return 0;
  39.         case 0:
  40.             scanf("%d", &s);
  41.             memset(tree,0,sizeof(tree));
  42.             break;
  43.         case 1:
  44.             int x,y,a;
  45.             scanf("%d %d %d", &x,&y,&a);
  46.  
  47.             sizes[0] = 0; xy = 0; A = x; B = x; only_contained = false;
  48.             gen(0, 0, s-1);
  49.             sizes[1] = 0; xy = 1; A = y; B = y; only_contained = false;
  50.             gen(0, 0, s-1);
  51.  
  52.             for(int i = sizes[0]-1; i >= 0; i--)
  53.                 for(int j = sizes[1]-1; j >= 0; j--) {
  54.                     int r0 = roots[0][i], r1 = roots[1][j];
  55.                     tree[r0][r1] += a;
  56.                 }
  57. /*
  58.             // Com o array isleaf, deveria ser:
  59.             for(int i = sizes[0]-1; i >= 0; i--)
  60.                 for(int j = sizes[1]-1; j >= 0; j--) {
  61.                     int r0 = roots[0][i], r1 = roots[1][j];
  62.  
  63.                     if(!isleaf[0][i])
  64.                         tree[r0][r1] = tree[2*r0+1][r1] + tree[2*r0+2][r1];
  65.                     else if(!isleaf[1][j])
  66.                         tree[r0][r1] = tree[r0][2*r1+1] + tree[r0][2*r1+2];
  67.                     else
  68.                         tree[r0][r1] += a;
  69.                 }
  70.             // Mas o TL no SPOJ é apertado e essa variação recebe só 85 pontos.
  71. */
  72.             break;
  73.         case 2:
  74.             int l,r,b,t;
  75.             scanf("%d %d %d %d", &l,&b,&r,&t);
  76.  
  77.             sizes[0] = 0; xy = 0; A = l; B = r; only_contained = true;
  78.             gen(0, 0, s-1);
  79.             sizes[1] = 0; xy = 1; A = b; B = t; only_contained = true;
  80.             gen(0, 0, s-1);
  81.  
  82.             int ans = 0;
  83.             for(int i = sizes[0]-1; i >= 0; i--)
  84.                 for(int j = sizes[1]-1; j >= 0; j--) {
  85.                     int r0 = roots[0][i], r1 = roots[1][j];
  86.                     ans += tree[r0][r1];
  87.                 }
  88.  
  89.             printf("%d\n", ans);
  90.             break;
  91.         }
  92.     }
  93.  
  94.     return 0;
  95. }
  96.  
  97.  
Time limit exceeded #stdin #stdout 5s 19112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2xyB5
language:
C++ (gcc 8.3)
created:
11 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!