Advertisement
jkonefal

Untitled

May 21st, 2023
1,189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.14 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[1005][1005];
  6. ll num;
  7.  
  8. pair <int, int> find(int x, int y) {
  9.     if (rep[x][y].first == x && rep[x][y].second == y) return make_pair(x, y);
  10.     rep[x][y] = find(rep[x][y].first, rep[x][y].second);
  11.     return rep[x][y];
  12. }
  13.  
  14. void uunion(int x1, int yjeden, int x2, int y2) {
  15.     if (rep[x1][yjeden] == rep[x2][y2]) return;
  16.     pair <int, int> p1 = find(x1, yjeden);
  17.     pair <int, int> p2 = find(x2, y2);
  18.     if (p1 == p2) return;
  19.     rep[p1.first][p1.second] = p2;
  20.     num--;
  21. }
  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.     map <ll, vector < pair <int, int>>> wart;
  29.     ll mx = 0;
  30.     cin >> n >> m;
  31.     for (int i = 0; i < n; i++)
  32.     {
  33.         for (int j = 0; j < m; j++)
  34.         {
  35.             cin >> ini[i][j];
  36.             rep[i][j] = make_pair(i, j);
  37.             wart[ini[i][j]].push_back(make_pair(i, j));
  38.             mx = max(ini[i][j], mx);
  39.         }
  40.     }
  41.  
  42.     cin >> t;
  43.     vector <ll> tests(t);
  44.     vector <ll> answ(t);
  45.     num = 0;
  46.     for (int i = 0; i < t; i++) cin >> tests[i];
  47.     ll cur = mx;
  48.     int g = t - 1;
  49.  
  50.     for (auto it = wart.rbegin(); it != wart.rend(); ++it)
  51.     {
  52.         while (g >= 0 && it->first <= tests[g]) answ[g] = num, g--;
  53.         ll a = tests[g];
  54.  
  55.         for (int k = 0; k < it->second.size(); k++)
  56.         {
  57.             int i = it->second[k].first;
  58.             int j = it->second[k].second;
  59.             num++;
  60.  
  61.             if (j > 0)
  62.             {
  63.                 if (ini[i][j - 1] > a) uunion(i, j, i, j - 1);
  64.             }
  65.             if (i > 0)
  66.             {
  67.                 if (ini[i - 1][j] > a) uunion(i, j, i - 1, j);
  68.             }
  69.             if (j < m - 1)
  70.             {
  71.                 if (ini[i][j + 1] > a) uunion(i, j, i, j + 1);
  72.             }
  73.             if (i < n - 1)
  74.             {
  75.                 if (ini[i + 1][j] > a) uunion(i, j, i + 1, j);
  76.             }
  77.         }
  78.     }
  79.  
  80.     while (g >= 0) answ[g] = num, g--;
  81.  
  82.     for (int i = 0; i < t; i++)
  83.     {
  84.         cout << answ[i] << " ";
  85.     }
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement