Advertisement
MinhNGUYEN2k4

Untitled

Sep 14th, 2021
1,040
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.62 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. //#define int long long
  3. #define double long double
  4. #define Task "ISLANDS"
  5. #define READFILE freopen(Task".inp", "r", stdin)
  6. #define WRITEFILE freopen(Task".out", "w", stdout)
  7. #define double long double
  8. #define oo 0x3f3f3f3f3f
  9. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define X first
  13. #define Y second
  14. #define watch(x) cout << (#x) << " = " << x << endl
  15. #define debug(x) cout << (#x) << " = " << x << endl
  16. #define all(x) x.begin(), x.end()
  17. #define sz(x) x.size()
  18. #define endl '\n'
  19. #define max3(a,b,c) max(max(a, b), c)
  20. #define max4(a,b,c,d) max(max(a, b), max(c, d))
  21. #define min4(a,b,c,d) min(min(a, b), min(c, d))
  22. #define debug4(a,b,c,d) watch(a);watch(b);watch(c);watch(d)
  23. #define ever (;true;)
  24. #define maxn 505
  25.  
  26. #define PI 3.14159265
  27.  
  28. using namespace std;
  29.  
  30. typedef pair < int, int > ii;
  31. typedef pair < int, ii > iii;
  32. typedef pair < ii, ii > iiii;
  33. typedef vector < int > vi;
  34. typedef vector < ii > vii;
  35. typedef vector < vi > vvi;
  36. typedef vector < iii > viii;
  37. typedef vector < vii > vvii;
  38. typedef vector < iiii > viiii;
  39. typedef vector < vvi > vvvi;
  40.  
  41. const int N = 1e3 + 5;
  42. const int dx[] = {-1, 1, 0, 0};
  43. const int dy[] = {0, 0, -1, 1};
  44.  
  45. int m, n;
  46. viii a;
  47.  
  48. ii root[N][N];
  49.  
  50. int res = 0;
  51. bool Added[N][N];
  52.  
  53. ii Getroot(ii x){
  54.     if (root[x.X][x.Y] == ii(0, 0)) return x;
  55.     return root[x.X][x.Y] = Getroot(root[x.X][x.Y]);
  56. }
  57.  
  58. bool Union(ii x, ii y){
  59.     x = Getroot(x);
  60.     y = Getroot(y);
  61.     if (x == y) return 0;
  62.     root[x.X][x.Y] = y;
  63.     return 1;
  64. }
  65.  
  66. void Add(ii u){
  67.     if (Added[u.X][u.Y]) return;
  68.     Added[u.X][u.Y] = 1;
  69.     ++res;
  70.     for (int dir = 0; dir < 4; ++dir){
  71.         ii v = ii(u.X + dx[dir], u.Y + dy[dir]);
  72.         if (v.X < 1 || v.X > m || v.Y < 1 || v.Y > n || Added[v.X][v.Y] == 0) continue;
  73.         res -= Union(u, v);
  74.     }
  75. }
  76.  
  77. int T;
  78. int Query[100111];
  79. int ans[100111];
  80.  
  81. void init(){
  82.     FAST;
  83.     #ifndef ONLINE_JUDGE
  84.     READFILE;
  85.     WRITEFILE;
  86.     #endif // ONLINE_JUDGE
  87.     cin >> m >> n;
  88.     for (int i = 1; i <= m; ++i){
  89.         for (int j = 1; j <= n; ++j){
  90.             int x;
  91.             cin >> x;
  92.             a.pb(iii(x, ii(i, j)));
  93.         }
  94.     }
  95.     sort(all(a), greater < iii > ());
  96. }
  97.  
  98. signed main(){
  99.     init();
  100.     cin >> T;
  101.     for (int i = 1; i <= T; ++i) cin >> Query[i];
  102.     int j = 0;
  103.     for (int i = T; i >= 1; --i){
  104.         while (j < a.size() && a[j].X > Query[i]){
  105.             Add(a[j].Y);
  106.             ++j;
  107.         }
  108.         ans[i] = res;
  109.     }
  110.     for (int i = 1; i <= T; ++i) cout << ans[i] << ' ';
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement