fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. //Union_Find
  6. ll ufpar[3000000], ufrank[3000000], num[3000000];
  7. //初期化
  8. void ufinit(ll n){
  9. 	for(ll ii = 1; ii <= n; ii++){
  10. 		ufpar[ii] = ii;
  11. 		ufrank[ii] = 0;
  12. 		num[ii]=1;
  13. 	}
  14. }
  15. //木の根を求める
  16. ll uffind(long long x){
  17. 	if(ufpar[x] == x) {
  18. 		return x;
  19. 	} else {
  20. 		ufpar[x] = uffind(ufpar[x]);
  21. 		return ufpar[x];
  22. 	}
  23. }
  24. ll elem(long long x){
  25. 	return num[uffind(x)];
  26. }
  27. //併合
  28. void ufunite(long long x, long long y){
  29. 	x = uffind(x);
  30. 	y = uffind(y);
  31. 	if(x == y) return;
  32. 	if(ufrank[x] < ufrank[y]){
  33. 		ufpar[x] = y;
  34. 		num[y]+=num[x];
  35. 		num[x]=0;
  36. 	} else {
  37. 		ufpar[y] = x;
  38. 		num[x]+=num[y];
  39. 		num[y]=0;
  40. 		if(ufrank[x] == ufrank[y]) ufrank[y]++;
  41. 	}
  42. }
  43.  
  44.  
  45. int main() {
  46.     // your code goes here
  47.     ll h,w,i,j,k,l,a[1505][1505]={0},sum[1505][1505]={0},size[1505][1505]={0},memo,ans[150004];
  48.     char s[1505];
  49.     cin >> h >> w;
  50.     for(i=1;i<=150000;i++) ans[i]=1;
  51.     for(i=1;i<=h;i++){
  52.     	cin >> s;
  53.     	ll msum[1505]={0};
  54.     	for(j=1;j<=w;j++){
  55.     		if(s[j-1]=='#') a[i][j]=1;
  56.     		msum[j]=msum[j-1]+a[i][j];
  57.     		sum[i][j]=sum[i-1][j]+msum[j];
  58.     	}
  59.     }
  60.     if(sum[h][w]==0){
  61.     	ll qs;
  62.     	cin >> qs;
  63.     	for(i=0;i<qs;i++){
  64.     		ll xs,ys,ls;
  65.     		cin >> xs >> ys >> ls;
  66.     		cout << (h-ls+1)*(w-ls+1) << endl;
  67.     	}
  68.     	return 0;
  69.     }
  70.     for(k=1;k<=min(h,w);k++){
  71.     	for(i=1;i<=h-k+1;i++){
  72.     		for(j=1;j<=w-k+1;j++){
  73.     			memo=sum[i+k-1][j+k-1]-sum[i-1][j+k-1]-sum[i+k-1][j-1]+sum[i-1][j-1];
  74.     			if(memo==0) size[i][j]=k;
  75.     		}
  76.     	}
  77.     }
  78.     ll q,roop;
  79.     cin >> q;
  80.     vector<pair<ll, ll> > v[1505];
  81.     vector<pair<ll, ll> > g[1505];
  82.     for(roop=1;roop<=q;roop++){
  83.     	ll x,y,l;
  84.     	cin >> x >> y >> l;
  85.     	v[l].push_back(make_pair(roop,(x-1)*w+y));
  86.     }
  87.     ufinit(h*w);
  88.     for(i=1;i<=h;i++){
  89.     	for(j=1;j<w;j++){
  90.     		memo=(i-1)*w+j;
  91.     		if(min(size[i][j],size[i][j+1])==0) continue;
  92.     		g[min(size[i][j],size[i][j+1])].push_back(make_pair(memo, memo+1));
  93.     	}
  94.     }
  95.     for(i=1;i<h;i++){
  96.     	for(j=1;j<=w;j++){
  97.     		memo=(i-1)*w+j;
  98.     		if(min(size[i][j],size[i+1][j])==0) continue;
  99.     		g[min(size[i][j],size[i+1][j])].push_back(make_pair(memo, memo+w));
  100.     	}
  101.     }
  102.     for(i=min(h,w);i>=1;i--){
  103.     	for(j=0;j<g[i].size();j++){
  104.     		ufunite(g[i][j].first,g[i][j].second);
  105.     	}
  106.     	for(j=0;j<v[i].size();j++){
  107.     		ans[v[i][j].first]=elem(v[i][j].second);
  108.     	}
  109.     }
  110.     for(roop=1;roop<=q;roop++) cout << ans[roop] << endl;
  111.     return 0;
  112.  
  113. }
Success #stdin #stdout 0.02s 61972KB
comments (?)
stdin 
8 8
....#...
..#.....
......#.
#.......
...#....
.#......
.....#..
.......#
6
4 5 1
1 6 2
2 5 2
7 1 2
4 6 3
6 3 3
stdout 
56
2
14
6
2
1
https://ideone.com/x5tII4
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!