oj.uz

Submission #166949

# Submission time Handle Problem Language Result Execution time Memory
166949 2019-12-04T19:40:20 Z muhi1112 Strah (COCI18_strah) C++17
110 / 110
 846 ms 82192 KB 
#include <bits/stdc++.h>
using namespace std;

#define f1 first
#define s2 second
#define mp make_pair
#define pb push_back
#define ll long long 
#define fri(a) freopen(a,"r",stdin);
#define fro(a) freopen(a,"w",stdout);
const ll N=3e3+5;
const ll K=30;

ll n,m,dp[N][N],hist[N],ans;
pair<ll,ll>st[N][K];
char grid[N][N];

ll calc(ll i,ll j){
	return ((i*(i+1)*j*(j+1))/4);
}
void calctable(){
	for(ll i=1;i<N;i++){
		for(ll j=1;j<N;j++){
			dp[i][j]=dp[i-1][j]+calc(i,j);
		}
	}
}
void build(){
	for(ll i=1;i<=m;i++){
		st[i][0]={hist[i],i};
	}
	for(ll j=1;j<K;j++){
		for(ll i=1;i+(1<<j)<=N;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
pair<ll,ll> qmin(ll l,ll r){
	ll j=log2(r-l+1);
	return min(st[l][j],st[r-(1<<j)+1][j]);
}
ll solve(ll l,ll r){
	if(l>r){
		return 0;
	}
	//cout<<l<<" "<<r<<endl;
	if(l==r){
		//cout<<l<<"  "<<r<<endl;
		//cout<<calc(1,hist[l])<<endl;
		return calc(1,hist[l]);
	}
	pair<ll,ll> x=qmin(l,r);
	//cout<<l<<" "<<r<<" "<<x.f1<<" "<<x.s2<<endl;
	ll ans=0;
	ll left=solve(l,x.s2-1);
	ll right=solve(x.s2+1,r);
	ans=left+right;
	//cout<<ans<<endl;
	ans+=(dp[r-l+1][x.f1]-dp[x.s2-l][x.f1]-dp[r-x.s2][x.f1]);
	//cout<<r-l+1<<" "<<x.f1<<" "<<dp[r-l+1][x.f1]<<" "<<dp[x.s2-l][x.f1]<<" "<<dp[r-x.s2][x.f1]<<endl;
	//cout<<ans<<endl;
	return ans;
}
int32_t main(){
	//fri("in.txt");
	//fro("out.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	calctable();
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
			cin>>grid[i][j];
			if(grid[i][j]=='#'){
				hist[j]=0;
			}
			else hist[j]++;
			//cout<<grid[i][j]<<endl;
			//cout<<hist[j]<<" ";
		}
		//cout<<endl;
		build();
		//cout<<st[2][1].s2<<endl;
		ans+=solve(1,m);
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 72440 KB Output is correct
2 Correct 71 ms 72440 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 72504 KB Output is correct
2 Correct 71 ms 72500 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 73336 KB Output is correct
2 Correct 139 ms 73364 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 73292 KB Output is correct
2 Correct 137 ms 73340 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 73272 KB Output is correct
2 Correct 143 ms 73332 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 74872 KB Output is correct
2 Correct 553 ms 76860 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 76292 KB Output is correct
2 Correct 769 ms 78320 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 75016 KB Output is correct
2 Correct 598 ms 79800 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 77824 KB Output is correct
2 Correct 674 ms 78016 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 78456 KB Output is correct
2 Correct 846 ms 82192 KB Output is correct