fork download
copy 
  1. //Bài 4
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int INF = 1e9;
  6.  
  7. int m, n, Q;
  8. vector<vector<int>> a;
  9.  
  10. struct SquareInfo {
  11.     int rows;
  12.     int cols;
  13.     vector<int> diff;
  14.     multiset<int> allDiff;
  15. };
  16.  
  17. SquareInfo sq[5];
  18.  
  19. int getId(int k, int r, int c) {
  20.     return (r - 1) * sq[k].cols + (c - 1);
  21. }
  22.  
  23. int calcDiff(int k, int r, int c) {
  24.     int mn = INF;
  25.     int mx = -INF;
  26.  
  27.     for (int i = r; i < r + k; i++) {
  28.         for (int j = c; j < c + k; j++) {
  29.             mn = min(mn, a[i][j]);
  30.             mx = max(mx, a[i][j]);
  31.         }
  32.     }
  33.  
  34.     return mx - mn;
  35. }
  36.  
  37. void build() {
  38.     int limit = min(m, n);
  39.  
  40.     for (int k = 1; k <= limit; k++) {
  41.         sq[k].rows = m - k + 1;
  42.         sq[k].cols = n - k + 1;
  43.  
  44.         int total = sq[k].rows * sq[k].cols;
  45.         sq[k].diff.assign(total, 0);
  46.         sq[k].allDiff.clear();
  47.  
  48.         for (int r = 1; r <= sq[k].rows; r++) {
  49.             for (int c = 1; c <= sq[k].cols; c++) {
  50.                 int val = calcDiff(k, r, c);
  51.                 int id = getId(k, r, c);
  52.  
  53.                 sq[k].diff[id] = val;
  54.                 sq[k].allDiff.insert(val);
  55.             }
  56.         }
  57.     }
  58. }
  59.  
  60. void removeSquare(int k, int r, int c) {
  61.     int id = getId(k, r, c);
  62.     int oldVal = sq[k].diff[id];
  63.  
  64.     auto it = sq[k].allDiff.find(oldVal);
  65.     if (it != sq[k].allDiff.end()) {
  66.         sq[k].allDiff.erase(it);
  67.     }
  68. }
  69.  
  70. void addSquare(int k, int r, int c) {
  71.     int id = getId(k, r, c);
  72.     int newVal = calcDiff(k, r, c);
  73.  
  74.     sq[k].diff[id] = newVal;
  75.     sq[k].allDiff.insert(newVal);
  76. }
  77.  
  78. void updateCell(int x, int y, int val) {
  79.     int limit = min(m, n);
  80.  
  81.     for (int k = 1; k <= limit; k++) {
  82.         int r1 = max(1, x - k + 1);
  83.         int r2 = min(x, m - k + 1);
  84.  
  85.         int c1 = max(1, y - k + 1);
  86.         int c2 = min(y, n - k + 1);
  87.  
  88.         for (int r = r1; r <= r2; r++) {
  89.             for (int c = c1; c <= c2; c++) {
  90.                 removeSquare(k, r, c);
  91.             }
  92.         }
  93.     }
  94.  
  95.     a[x][y] = val;
  96.  
  97.     for (int k = 1; k <= limit; k++) {
  98.         int r1 = max(1, x - k + 1);
  99.         int r2 = min(x, m - k + 1);
  100.  
  101.         int c1 = max(1, y - k + 1);
  102.         int c2 = min(y, n - k + 1);
  103.  
  104.         for (int r = r1; r <= r2; r++) {
  105.             for (int c = c1; c <= c2; c++) {
  106.                 addSquare(k, r, c);
  107.             }
  108.         }
  109.     }
  110. }
  111.  
  112. int query(int T) {
  113.     int limit = min(m, n);
  114.     int ans = 0;
  115.  
  116.     for (int k = 1; k <= limit; k++) {
  117.         if (!sq[k].allDiff.empty()) {
  118.             int best = *sq[k].allDiff.begin();
  119.  
  120.             if (best <= T) {
  121.                 ans = k;
  122.             }
  123.         }
  124.     }
  125.  
  126.     return ans;
  127. }
  128.  
  129. int main() {
  130.  
  131.     freopen("khuvuonanhsang.inp","r",stdin);
  132.     freopen("khuvuonanhsang.out","w",stdout);
  133.     cin >> m >> n >> Q;
  134.  
  135.     a.assign(m + 1, vector<int>(n + 1));
  136.  
  137.     for (int i = 1; i <= m; i++) {
  138.         for (int j = 1; j <= n; j++) {
  139.             cin >> a[i][j];
  140.         }
  141.     }
  142.  
  143.     build();
  144.  
  145.     while (Q--) {
  146.         int type;
  147.         cin >> type;
  148.  
  149.         if (type == 1) {
  150.             int i, j, X;
  151.             cin >> i >> j >> X;
  152.  
  153.             updateCell(i, j, X);
  154.         } else {
  155.             int T;
  156.             cin >> T;
  157.  
  158.             cout << query(T) << '\n';
  159.         }
  160.     }
  161.  
  162.     return 0;
  163. }
  164.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IrXJdi
language:
C++ (gcc 8.3)
created:
3 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!