Advertisement
jkonefal

Untitled

May 22nd, 2023
798
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int rep[1000005];
  4. int ini[1000005];
  5. int num;
  6. int n, m, t;
  7.  
  8. int ptn(int x, int y) {
  9.     return x * m + y;
  10. }
  11.  
  12. pair <int, int> ntp(int x) {
  13.     return make_pair(x / m, x % m);
  14. }
  15.  
  16. int find(int x, int y) {
  17.     if (ntp(rep[ptn(x, y)]).first == x && ntp(rep[ptn(x, y)]).second == y) return ptn(x, y);
  18.     rep[ptn(x, y)] = find(ntp(rep[ptn(x, y)]).first, ntp(rep[ptn(x, y)]).second);
  19.     return rep[ptn(x, y)];
  20. }
  21.  
  22. void uunion(int x1, int yjeden, int x2, int y2) {
  23.     if (rep[ptn(x1, yjeden)] == rep[ptn(x2, y2)]) return;
  24.     int p1 = find(x1, yjeden);
  25.     int p2 = find(x2, y2);
  26.     if (p1 == p2) return;
  27.     rep[p1] = p2;
  28.     num--;
  29. }
  30.  
  31. int main() {
  32.     ios_base::sync_with_stdio(0);
  33.     cin.tie(0);
  34.     cout.tie(0);
  35.     //map <int, vector <int>> wart;
  36.     priority_queue < pair<int, int>> wart;
  37.     int mx = 0;
  38.     cin >> n >> m;
  39.     for (int i = 0; i < n; i++)
  40.     {
  41.         for (int j = 0; j < m; j++)
  42.         {
  43.             cin >> ini[ptn(i, j)];
  44.             rep[ptn(i, j)] = ptn(i, j);
  45.             wart.push(make_pair(ini[ptn(i, j)], ptn(i, j)));
  46.             mx = max(ini[ptn(i, j)], mx);
  47.         }
  48.     }
  49.  
  50.     cin >> t;
  51.     vector <int> tests(t);
  52.     vector <int> answ(t);
  53.     num = 0;
  54.     for (int i = 0; i < t; i++) cin >> tests[i];
  55.     int g = t - 1;
  56.  
  57.     // for (auto it = wart.rbegin(); it != wart.rend(); ++it)
  58.     while (!wart.empty())
  59.     {
  60.         pair <int, int> cur = wart.top();
  61.         int val = cur.first;
  62.         //cout << val << '\n';
  63.         while (g >= 0 && val <= tests[g]) answ[g] = num, g--;
  64.  
  65.         int a = tests[g];
  66.         int i = ntp(cur.second).first;
  67.         int j = ntp(cur.second).second;
  68.         num++;
  69.  
  70.         if (j > 0)
  71.         {
  72.             if (ini[ptn(i, j - 1)] > a) uunion(i, j, i, j - 1);
  73.         }
  74.         if (i > 0)
  75.         {
  76.             if (ini[ptn(i - 1, j)] > a) uunion(i, j, i - 1, j);
  77.         }
  78.         if (j < m - 1)
  79.         {
  80.             if (ini[ptn(i, j + 1)] > a) uunion(i, j, i, j + 1);
  81.         }
  82.         if (i < n - 1)
  83.         {
  84.             if (ini[ptn(i + 1, j)] > a) uunion(i, j, i + 1, j);
  85.         }
  86.         wart.pop();
  87.     }
  88.  
  89.     while (g >= 0) answ[g] = num, g--;
  90.  
  91.     for (int i = 0; i < t; i++)
  92.     {
  93.         cout << answ[i] << " ";
  94.     }
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement