Advertisement
jkonefal

Untitled

May 20th, 2023
862
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. pair<int, int> rep[1005][1005];
  5. ll ini[105][105];
  6. bool used[1005][1005];
  7. ll num;
  8.  
  9. pair <int, int> find(int x, int y) {
  10.     if (rep[x][y].first == x && rep[x][y].second == y) return make_pair(x, y);
  11.     rep[x][y] = find(rep[x][y].first, rep[x][y].second);
  12.     return rep[x][y];
  13. }
  14.  
  15. void uunion(int x1, int yjeden, int x2, int y2) {
  16.     if (rep[x1][yjeden] == rep[x2][y2]) return;
  17.     pair <int, int> p1 = find(x1, yjeden);
  18.     pair <int, int> p2 = find(x2, y2);
  19.     if (p1 == p2) return;
  20.     rep[p1.first][p1.second] = p2;
  21.     num--;
  22. }
  23. int main() {
  24.     ios_base::sync_with_stdio(0);
  25.     cin.tie(0);
  26.     cout.tie(0);
  27.     int n, m, t;
  28.     cin >> n >> m;
  29.     for (int i = 0; i < n; i++)
  30.     {
  31.         for (int j = 0; j < m; j++)
  32.         {
  33.             cin >> ini[i][j];
  34.             rep[i][j] = make_pair(i, j);
  35.             used[i][j] = false;
  36.         }
  37.     }
  38.  
  39.     cin >> t;
  40.     vector <ll> tests(t);
  41.     vector <ll> answ(t);
  42.     num = 0;
  43.     for (int i = 0; i < t; i++) cin >> tests[i];
  44.  
  45.     for (int g = t - 1; g >= 0; g--)
  46.     {
  47.         ll a = tests[g];
  48.         for (int i = 0; i < t; i++)
  49.         {
  50.             for (int i = 0; i < n; i++)
  51.             {
  52.                 for (int j = 0; j < m; j++)
  53.                 {
  54.                     if (ini[i][j] <= a) continue;
  55.  
  56.                     if (!used[i][j]) num++;
  57.  
  58.                     if (j > 0)
  59.                     {
  60.                         if (ini[i][j - 1] > a) uunion(i, j, i, j - 1);
  61.                     }
  62.                     if (i > 0)
  63.                     {
  64.                         if (ini[i - 1][j] > a) uunion(i, j, i - 1, j);
  65.                     }
  66.                     used[i][j] = true;
  67.                 }
  68.             }
  69.             answ[g] = num;
  70.         }
  71.     }
  72.     for (int i = 0; i < t; i++) cout << answ[i] << " ";
  73.     cout << '\n';
  74.  
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement