Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ii pair<int,int>
- #define iii pair<int,ii>
- #define fi first
- #define se second
- using namespace std;
- int n, m, a[1005][1005];
- int t;
- int q[100005];
- vector<iii> node;
- bool vst[1005][1005];
- int dx[4] = {1,-1,0,0};
- int dy[4] = {0,0,1,-1};
- int par[1005*1005];
- int cnt;
- int kq[100005];
- int get(int u){
- return (u==par[u] ? u : par[u]=get(par[u]));
- }
- void join(int u, int v){
- u = get(u);
- v = get(v);
- if (u==v) return;
- par[v] = u;
- cnt--;
- }
- bool ok(int u, int v){
- if (1 <= u && u <= n && 1 <= v && v <= m) return true;
- return false;
- }
- int main()
- {
- if (fopen("test.inp","r")) freopen("test.inp","r",stdin);
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- cin >> n >> m;
- for(int i=1; i<=n; i++){
- for(int j=1; j<=m; j++){
- cin >> a[i][j];
- node.push_back(iii(a[i][j],ii(i,j)));
- }
- }
- cin >> t;
- for(int i=1; i<=t; i++) cin >> q[i];
- for(int i=1; i<=n*m; i++) par[i] = i;
- sort(node.begin(),node.end(),greater<iii>());
- int j=0;
- for(int i=t; i>=1; i--){
- while (j<(int)node.size() && node[j].fi > q[i]){
- int u = node[j].se.fi;
- int v = node[j].se.se;
- vst[u][v] = true;
- ++cnt;
- for(int k=0; k<4; k++){
- int x = u + dx[k];
- int y = v + dy[k];
- if (ok(x,y) && vst[x][y]) join((u-1)*m+v,(x-1)*m+y);
- }
- j++;
- }
- kq[i] = cnt;
- }
- for(int i=1; i<=t; i++) cout << kq[i] << ' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement