fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void *wmem;
  5. char memarr[96000000];
  6. template<class S, class T> inline S min_L(S a,T b){
  7.   return a<=b?a:b;
  8. }
  9. template<class S, class T> inline S max_L(S a,T b){
  10.   return a>=b?a:b;
  11. }
  12. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  13.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  14.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  15.   (*arr)=(T*)(*mem);
  16.   (*mem)=((*arr)+x);
  17. }
  18. template<class T> void malloc2d(T ***arr, int x, int y){
  19.   int i;
  20.   (*arr) = (T**)malloc(x*sizeof(T*));
  21.   (*arr)[0] = (T*)malloc(x*y*sizeof(T));
  22.   int jZyWAPpY = x;
  23.   for(i=(1);i<(jZyWAPpY);i++){
  24.     (*arr)[i]=(*arr)[i-1]+y;
  25.   }
  26. }
  27. template<class T> void free2d(T **arr){
  28.   free(arr[0]);
  29.   free(arr);
  30. }
  31. template <class T> struct DijkstraHeap{
  32.   int *hp;
  33.   int *place;
  34.   int size;
  35.   char *visited;
  36.   T *val;
  37.   void malloc(int N){
  38.     hp = (int*)std::malloc(N*sizeof(int));
  39.     place = (int*)std::malloc(N*sizeof(int));
  40.     visited = (char*)std::malloc(N*sizeof(char));
  41.     val = (T*)std::malloc(N*sizeof(T));
  42.   }
  43.   void free(){
  44.     std::free(hp);
  45.     std::free(place);
  46.     std::free(visited);
  47.     std::free(val);
  48.   }
  49.   void walloc(int N, void **mem=&wmem){
  50.     walloc1d(&hp, N, mem);
  51.     walloc1d(&place, N, mem);
  52.     walloc1d(&visited, N, mem);
  53.     walloc1d(&val, N, mem);
  54.   }
  55.   void init(int N){
  56.     int i;
  57.     size = 0;
  58.     for(i=(0);i<(N);i++){
  59.       place[i]=-1;
  60.     }
  61.     for(i=(0);i<(N);i++){
  62.       visited[i]=0;
  63.     }
  64.   }
  65.   void up(int n){
  66.     int m;
  67.     while(n){
  68.       m=(n-1)/2;
  69.       if(val[hp[m]]<=val[hp[n]]){
  70.         break;
  71.       }
  72.       swap(hp[m],hp[n]);
  73.       swap(place[hp[m]],place[hp[n]]);
  74.       n=m;
  75.     }
  76.   }
  77.   void down(int n){
  78.     int m;
  79.     for(;;){
  80.       m=2*n+1;
  81.       if(m>=size){
  82.         break;
  83.       }
  84.       if(m+1<size&&val[hp[m]]>val[hp[m+1]]){
  85.         m++;
  86.       }
  87.       if(val[hp[m]]>=val[hp[n]]){
  88.         break;
  89.       }
  90.       swap(hp[m],hp[n]);
  91.       swap(place[hp[m]],place[hp[n]]);
  92.       n=m;
  93.     }
  94.   }
  95.   void change(int n, T v){
  96.     if(visited[n]||(place[n]>=0&&val[n]<=v)){
  97.       return;
  98.     }
  99.     val[n]=v;
  100.     if(place[n]==-1){
  101.       place[n]=size;
  102.       hp[size++]=n;
  103.       up(place[n]);
  104.     }
  105.     else{
  106.       up(place[n]);
  107.     }
  108.   }
  109.   int pop(void){
  110.     int res=hp[0];
  111.     place[res]=-1;
  112.     size--;
  113.     if(size){
  114.       hp[0]=hp[size];
  115.       place[hp[0]]=0;
  116.       down(0);
  117.     }
  118.     visited[res]=1;
  119.     return res;
  120.   }
  121. }
  122. ;
  123. template<class T> struct Grid2d{
  124.   int r;
  125.   int c;
  126.   T **d;
  127.   int set_s;
  128.   int set_d;
  129.   T **d_s;
  130.   int **up;
  131.   int **dw;
  132.   int **lf;
  133.   int **rg;
  134.   void malloc(const int rr, const int cc){
  135.     r = rr;
  136.     c = cc;
  137.     set_s = 0;
  138.     set_d = 0;
  139.     malloc2d(&d, r, c);
  140.   }
  141.   void free(void){
  142.     free2d(d);
  143.     if(set_s){
  144.       free2d(d_s);
  145.     }
  146.     if(set_d){
  147.       free2d(up);
  148.       free2d(dw);
  149.       free2d(lf);
  150.       free2d(rg);
  151.     }
  152.   }
  153.   T*operator[](int a){
  154.     return d[a];
  155.   }
  156.   void setSum(void){
  157.     int i;
  158.     int j;
  159.     if(set_s == 0){
  160.       set_s = 1;
  161.       malloc2d(&d_s, r+1, c+1);
  162.     }
  163.     for(i=(0);i<(r+1);i++){
  164.       d_s[i][0] = 0;
  165.     }
  166.     for(j=(0);j<(c+1);j++){
  167.       d_s[0][j] = 0;
  168.     }
  169.     for(i=(0);i<(r);i++){
  170.       for(j=(0);j<(c);j++){
  171.         d_s[i+1][j+1] = d_s[i][j+1] + d_s[i+1][j] - d_s[i][j] + d[i][j];
  172.       }
  173.     }
  174.   }
  175.   void setDir(void){
  176.     int i;
  177.     int j;
  178.     if(set_d == 0){
  179.       set_d = 1;
  180.       malloc2d(&up, r, c);
  181.       malloc2d(&dw, r, c);
  182.       malloc2d(&lf, r, c);
  183.       malloc2d(&rg, r, c);
  184.     }
  185.     for(j=(0);j<(c);j++){
  186.       up[0][j] = 1;
  187.     }
  188.     for(i=(1);i<(r);i++){
  189.       for(j=(0);j<(c);j++){
  190.         if(d[i][j]==d[i-1][j]){
  191.           up[i][j] = 1 + up[i-1][j];
  192.         }
  193.         else{
  194.           up[i][j] = 1 ;
  195.         }
  196.       }
  197.     }
  198.     for(j=(0);j<(c);j++){
  199.       dw[r-1][j] = 1;
  200.     }
  201.     for(i=r-2;i>=0;i--){
  202.       for(j=(0);j<(c);j++){
  203.         if(d[i][j]==d[i+1][j]){
  204.           dw[i][j] = 1 + dw[i+1][j];
  205.         }
  206.         else{
  207.           dw[i][j] = 1 ;
  208.         }
  209.       }
  210.     }
  211.     for(i=(0);i<(r);i++){
  212.       lf[i][0] = 1;
  213.       for(j=(1);j<(c);j++){
  214.         if(d[i][j]==d[i][j-1]){
  215.           lf[i][j] = 1 + lf[i][j-1];
  216.         }
  217.         else{
  218.           lf[i][j] = 1 ;
  219.         }
  220.       }
  221.     }
  222.     for(i=(0);i<(r);i++){
  223.       rg[i][c-1] = 1;
  224.       for(j=c-2;j>=0;j--){
  225.         if(d[i][j]==d[i][j+1]){
  226.           rg[i][j] = 1 + rg[i][j+1];
  227.         }
  228.         else{
  229.           rg[i][j] = 1 ;
  230.         }
  231.       }
  232.     }
  233.   }
  234.   void setDirMatch(const T v){
  235.     int i;
  236.     int j;
  237.     if(set_d == 0){
  238.       set_d = 1;
  239.       malloc2d(&up, r, c);
  240.       malloc2d(&dw, r, c);
  241.       malloc2d(&lf, r, c);
  242.       malloc2d(&rg, r, c);
  243.     }
  244.     for(j=(0);j<(c);j++){
  245.       if(d[0][j]==v){
  246.         up[0][j] =1;
  247.       }
  248.       else{
  249.         up[0][j] =0;
  250.       }
  251.     }
  252.     for(i=(1);i<(r);i++){
  253.       for(j=(0);j<(c);j++){
  254.         if(d[i][j]==v){
  255.           up[i][j] =1 + up[i-1][j];
  256.         }
  257.         else{
  258.           up[i][j] =0;
  259.         }
  260.       }
  261.     }
  262.     for(j=(0);j<(c);j++){
  263.       if(d[r-1][j]==v){
  264.         dw[r-1][j] =1;
  265.       }
  266.       else{
  267.         dw[r-1][j] =0;
  268.       }
  269.     }
  270.     for(i=r-2;i>=0;i--){
  271.       for(j=(0);j<(c);j++){
  272.         if(d[i][j]==v){
  273.           dw[i][j] =1 + dw[i+1][j];
  274.         }
  275.         else{
  276.           dw[i][j] =0;
  277.         }
  278.       }
  279.     }
  280.     for(i=(0);i<(r);i++){
  281.       if(d[i][0]==v){
  282.         lf[i][0] =1;
  283.       }
  284.       else{
  285.         lf[i][0] =0;
  286.       }
  287.       for(j=(1);j<(c);j++){
  288.         if(d[i][j]==v){
  289.           lf[i][j] =1 + lf[i][j-1];
  290.         }
  291.         else{
  292.           lf[i][j] =0;
  293.         }
  294.       }
  295.     }
  296.     for(i=(0);i<(r);i++){
  297.       if(d[i][c-1]==v){
  298.         rg[i][c-1] =1;
  299.       }
  300.       else{
  301.         rg[i][c-1] =0;
  302.       }
  303.       for(j=c-2;j>=0;j--){
  304.         if(d[i][j]==v){
  305.           rg[i][j] =1 + rg[i][j+1];
  306.         }
  307.         else{
  308.           rg[i][j] =0;
  309.         }
  310.       }
  311.     }
  312.   }
  313.   inline T getSum(const int r1, const int c1, const int r2, const int c2){
  314.     return d_s[r2+1][c2+1] - d_s[r1][c2+1] - d_s[r2+1][c1] + d_s[r1][c1];
  315.   }
  316.   template<class S> inline void getDist4(int sr, int sc, S **res, void *mem = wmem){
  317.     int i;
  318.     int j;
  319.     int k;
  320.     DijkstraHeap<S> hp;
  321.     hp.walloc(r*c);
  322.     hp.init(r*c);
  323.     if(d[sr][sc] >= 0){
  324.       hp.change(sr*c+sc, d[sr][sc]);
  325.     }
  326.     while(hp.size){
  327.       k = hp.pop();
  328.       i = k / c;
  329.       j = k % c;
  330.       if(i-1 >= 0 && d[i-1][j] >= 0){
  331.         hp.change((i-1)*c+j, hp.val[k]+d[i-1][j]);
  332.       }
  333.       if(i+1 <  r && d[i+1][j] >= 0){
  334.         hp.change((i+1)*c+j, hp.val[k]+d[i+1][j]);
  335.       }
  336.       if(j-1 >= 0 && d[i][j-1] >= 0){
  337.         hp.change(i*c+(j-1), hp.val[k]+d[i][j-1]);
  338.       }
  339.       if(j+1 <  c && d[i][j+1] >= 0){
  340.         hp.change(i*c+(j+1), hp.val[k]+d[i][j+1]);
  341.       }
  342.     }
  343.     for(i=(0);i<(r);i++){
  344.       for(j=(0);j<(c);j++){
  345.         if(hp.visited[i*c+j]){
  346.           res[i][j] =hp.val[i*c+j];
  347.         }
  348.         else{
  349.           res[i][j] =-1;
  350.         }
  351.       }
  352.     }
  353.   }
  354. }
  355. ;
  356. #define main dummy_main
  357. int main(){
  358.   wmem = memarr;
  359.   return 0;
  360. }
  361. #undef main
  362. int x;
  363. int y;
  364. Grid2d<int> g;
  365. class Solution{
  366.   public:
  367.   vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K){
  368.     int cTE1_r3A, i, xr20shxY;
  369.     vector<vector<int>> res;
  370.     vector<int> tmp;
  371.     dummy_main();
  372.     x = mat.size();
  373.     y = mat[0].size();
  374.     g.malloc(x,y);
  375.     for(i=(0);i<(x);i++){
  376.       int j;
  377.       for(j=(0);j<(y);j++){
  378.         g[i][j] = mat[i][j];
  379.       }
  380.     }
  381.     g.setSum();
  382.     for(cTE1_r3A=(0);cTE1_r3A<(y);cTE1_r3A++){
  383.       tmp.push_back(0);
  384.     }
  385.     for(xr20shxY=(0);xr20shxY<(x);xr20shxY++){
  386.       res.push_back(tmp);
  387.     }
  388.     for(i=(0);i<(x);i++){
  389.       int j;
  390.       for(j=(0);j<(y);j++){
  391.         res[i][j] = g.getSum(max_L(0, i-K),max_L(0, j-K),min_L(x-1, i+K),min_L(y-1, j+K));
  392.       }
  393.     }
  394.     g.free();
  395.     return res;
  396.   }
  397. }
  398. ;
  399. // cLay varsion 20200112-1
  400.  
  401. // --- original code ---
  402. // #define main dummy_main
  403. // {}
  404. // #undef main
  405. // 
  406. // int x, y;
  407. // Grid2d<int> g;
  408. // 
  409. // class Solution {
  410. // public:
  411. //   vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
  412. //     vector<vector<int>> res;
  413. //     vector<int> tmp;
  414. //     dummy_main();
  415. //     x = mat.size();
  416. //     y = mat[0].size();
  417. //     g.malloc(x,y);
  418. //     rep(i,x) rep(j,y) g[i][j] = mat[i][j];
  419. //     g.setSum();
  420. // 
  421. //     rep(y) tmp.push_back(0);
  422. //     rep(x) res.push_back(tmp);
  423. // 
  424. //     rep(i,x) rep(j,y) res[i][j] = g.getSum(max(0,i-K), max(0,j-K), min(x-1,i+K), min(y-1,j+K));
  425. // 
  426. //     g.free();
  427. //     return res;
  428. //   }
  429. // };
  430.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/5X45yU
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!