Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- //#define int long long
- #define double long double
- #define Task "ISLANDS"
- #define READFILE freopen(Task".inp", "r", stdin)
- #define WRITEFILE freopen(Task".out", "w", stdout)
- #define double long double
- #define oo 0x3f3f3f3f3f
- #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
- #define mp make_pair
- #define pb push_back
- #define X first
- #define Y second
- #define watch(x) cout << (#x) << " = " << x << endl
- #define debug(x) cout << (#x) << " = " << x << endl
- #define all(x) x.begin(), x.end()
- #define sz(x) x.size()
- #define endl '\n'
- #define max3(a,b,c) max(max(a, b), c)
- #define max4(a,b,c,d) max(max(a, b), max(c, d))
- #define min4(a,b,c,d) min(min(a, b), min(c, d))
- #define debug4(a,b,c,d) watch(a);watch(b);watch(c);watch(d)
- #define ever (;true;)
- #define maxn 505
- #define PI 3.14159265
- using namespace std;
- typedef pair < int, int > ii;
- typedef pair < int, ii > iii;
- typedef pair < ii, ii > iiii;
- typedef vector < int > vi;
- typedef vector < ii > vii;
- typedef vector < vi > vvi;
- typedef vector < iii > viii;
- typedef vector < vii > vvii;
- typedef vector < iiii > viiii;
- typedef vector < vvi > vvvi;
- const int N = 1e3 + 5;
- const int dx[] = {-1, 1, 0, 0};
- const int dy[] = {0, 0, -1, 1};
- int m, n;
- viii a;
- ii root[N][N];
- int res = 0;
- bool Added[N][N];
- ii Getroot(ii x){
- if (root[x.X][x.Y] == ii(0, 0)) return x;
- return root[x.X][x.Y] = Getroot(root[x.X][x.Y]);
- }
- bool Union(ii x, ii y){
- x = Getroot(x);
- y = Getroot(y);
- if (x == y) return 0;
- root[x.X][x.Y] = y;
- return 1;
- }
- void Add(ii u){
- if (Added[u.X][u.Y]) return;
- Added[u.X][u.Y] = 1;
- ++res;
- for (int dir = 0; dir < 4; ++dir){
- ii v = ii(u.X + dx[dir], u.Y + dy[dir]);
- if (v.X < 1 || v.X > m || v.Y < 1 || v.Y > n || Added[v.X][v.Y] == 0) continue;
- res -= Union(u, v);
- }
- }
- int T;
- int Query[100111];
- int ans[100111];
- void init(){
- FAST;
- #ifndef ONLINE_JUDGE
- READFILE;
- WRITEFILE;
- #endif // ONLINE_JUDGE
- cin >> m >> n;
- for (int i = 1; i <= m; ++i){
- for (int j = 1; j <= n; ++j){
- int x;
- cin >> x;
- a.pb(iii(x, ii(i, j)));
- }
- }
- sort(all(a), greater < iii > ());
- }
- signed main(){
- init();
- cin >> T;
- for (int i = 1; i <= T; ++i) cin >> Query[i];
- int j = 0;
- for (int i = T; i >= 1; --i){
- while (j < a.size() && a[j].X > Query[i]){
- Add(a[j].Y);
- ++j;
- }
- ans[i] = res;
- }
- for (int i = 1; i <= T; ++i) cout << ans[i] << ' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement