fork download
copy 
  1. #include<stdio.h>
  2. #include<unordered_map>
  3. #include<vector>
  4. using namespace std;
  5. int offset[109];
  6. int increaseRange[109];
  7. inline int nmtoid(int n, int m){
  8.     if(n==1)return m-1;
  9.     if(n==2)return m+8;
  10.     if(n==3)return m+12;
  11.     if(n==4)return m+15;
  12.     return m+17+n-5;
  13. }
  14. inline int encode(int nmid, int di, int dj){
  15.     return (nmid * 9 + di) * 9 + dj;
  16. }
  17. inline void decode(int id, int& nmid, int& di, int& dj)
  18. {
  19.     dj = id%9; id/=9;
  20.     di = id%9; id/=9;
  21.     nmid = id;
  22. }
  23. struct QType{
  24.     int id;
  25.     int of;
  26. };
  27. int n, m;
  28. vector<QType> qlist[509][509];
  29. void inil(){
  30.     int i, j, k, l;
  31.     offset[1] = 1;
  32.     increaseRange[1] = 1;
  33.     for(i=2;i<=9;i++){
  34.         offset[i] = offset[i-1] * 6;
  35.         increaseRange[i] = increaseRange[i-1] * 6 + 1;
  36.     }
  37.     for(i=0;i<n;i++){
  38.         for(j=0;j<m;j++){
  39.             for(k=1;k<=9;k++){
  40.                 if(i+k<=n){
  41.                 for(l=1;l<=9;l++){
  42.                     if(k*l <= 9 && j+l<=m){
  43.                         for(int di = 0; di < k; di++){
  44.                             for(int dj = 0; dj < l; dj++){
  45.                                 QType q;
  46.                                 q.id = encode(nmtoid(k, l), di, dj);
  47.                                 q.of = offset[di * l + dj + 1];
  48.                                 qlist[i+di][j+dj].push_back(q);
  49.                             }
  50.                         }
  51.                     }
  52.                 }
  53.                 }
  54.             }
  55.         }
  56.     }
  57. }
  58. int a[509][509];
  59. int v[23][509][509];
  60. unordered_map<int, int> ap[23];
  61. int main()
  62. {
  63.     int i, j, k;
  64.     scanf("%d %d",&n,&m);
  65.     inil();
  66.     for(i=0;i<n;i++){
  67.         for(j=0;j<m;j++){
  68.             scanf("%d",&a[i][j]);
  69.             a[i][j]--;
  70.             if(a[i][j]>0){
  71.             for(auto& q : qlist[i][j]){
  72.                 int nmid;
  73.                 int di;
  74.                 int dj;
  75.                 decode(q.id, nmid, di, dj);
  76.                 v[nmid][i-di][j-dj] += q.of * a[i][j];
  77.             }
  78.             }
  79.         }
  80.     }
  81.     for(k=0;k<23;k++){
  82.         for(i=0;i<n;i++){
  83.             for(j=0;j<m;j++){
  84.                 ap[k][v[k][i][j]]++;
  85.             }
  86.         }
  87.     }
  88.     int ql;
  89.     scanf("%d",&ql);
  90.     while(ql--){
  91.         int cmd;
  92.         scanf("%d",&cmd);
  93.         if(cmd==1){
  94.             scanf("%d %d %d",&i,&j,&k);
  95.             i--;j--;k--;
  96.             if(a[i][j] != k){
  97.                 int dk = k - a[i][j];
  98.                 a[i][j] = k;
  99.                 for(const auto& q : qlist[i][j]){
  100.                     int nmid;
  101.                     int di;
  102.                     int dj;
  103.                     decode(q.id, nmid, di, dj);
  104.                     int& me = v[nmid][i-di][j-dj];
  105.                     ap[nmid][me]--;
  106.                     me += q.of * dk;
  107.                     ap[nmid][me]++;
  108.                 }
  109.             }
  110.         }
  111.         else{
  112.             int r, c;
  113.             scanf("%d %d",&r,&c);
  114.             int rcid = nmtoid(r,c);
  115.             int me = 0;
  116.             int xk=0;
  117.             int mk=5;
  118.             for(i=0;i<r*c;i++){
  119.                 scanf("%d",&k);
  120.                 if(xk<k)xk=k;
  121.                 if(mk>k)mk=k;
  122.                 me+=k*offset[i+1];
  123.             }
  124.             int res=0;
  125.             for(int l = -mk; l < 5-xk; l++){
  126.                 int te = me + l * increaseRange[r*c];
  127.                 auto iter = ap[rcid].find(te);
  128.                 if(iter != ap[rcid].end()){
  129.                     res += iter->second;
  130.                 }
  131.             }
  132.             printf("%d\n", res);
  133.         }
  134.     }
  135. }
  136.  
Success #stdin #stdout 0.01s 17816KB
comments (?)
stdin
copy 
2 3
1 2 3
2 4 3
7
2 2 2 0 1 1 5
1 2 2 3
1 2 3 4
2 1 2 4 5
2 2 1 2 3
2 1 1 5
2 2 2 1 2 2 3
stdout
copy 
0
4
3
6
2
https://ideone.com/42ObyZ
language:
C++14 (gcc 8.3)
created:
5 days 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!