oj.uz

Submission #756612

# Submission time Handle Problem Language Result Execution time Memory
756612 2023-06-12T01:46:11 Z pcc Strah (COCI18_strah) C++14
110 / 110
 306 ms 35988 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const int mxn = 2020;
ll arr[mxn][mxn];
ll ans = 0;
int n,m;
int dsu[mxn],sz[mxn],lef[mxn],rig[mxn];
ll dp[mxn];
ll tag = 0;

int root(int k){
	return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
	a = root(a),b= root(b);
	if(a == b)return;
	tag = tag-dp[rig[a]-lef[a]+1];
	tag = tag-dp[rig[b]-lef[b]+1];
	if(sz[b]>sz[a])swap(a,b);
	dsu[b] = a;
	sz[a] += sz[b];
	lef[a] = min(lef[a],lef[b]);
	rig[a] = max(rig[a],rig[b]);
	tag = tag+dp[rig[a]-lef[a]+1];
}

void calc(int id){
	vector<int> v[mxn];
	tag = 0;
	for(int i = 1;i<=m;i++){
		v[arr[id][i]].push_back(i);
	}
	for(int i = 1;i<=m;i++){
		lef[i] = rig[i] = i;
		dsu[i] = i;
		sz[i] = 1;
	}
	for(int i = mxn-1;i>=1;i--){
		for(auto &j:v[i]){
			tag++;
			if(arr[id][j-1] >= i)onion(j-1,j);
			if(arr[id][j+1] >= i)onion(j,j+1);
			//cout<<j<<','<<i<<','<<lef[root(j)]<<' '<<rig[root(j)]<<endl;
		}
		ans += tag*i;
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=n;i++)arr[i][0] = -1;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			char c;
			cin>>c;
			if(c == '#')arr[i][j] = 0;
			else arr[i][j] = arr[i-1][j]+1;
		}
	}
	dp[1] = 1;
	ll tmp = 1;
	for(int i = 2;i<mxn;i++){
		tmp += i;
		dp[i] = dp[i-1]+tmp;
	}
	//for(int i = 1;i<10;i++)cout<<dp[i]<<' ';cout<<endl;
	for(int i = 1;i<=n;i++){
		calc(i);
		//cout<<i<<":"<<ans<<','<<endl;
	}
	cout<<ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2344 KB Output is correct
2 Correct 10 ms 2392 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2344 KB Output is correct
2 Correct 10 ms 2388 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2404 KB Output is correct
2 Correct 12 ms 2520 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 12980 KB Output is correct
2 Correct 169 ms 26712 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 23856 KB Output is correct
2 Correct 234 ms 34776 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 15444 KB Output is correct
2 Correct 170 ms 28428 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10068 KB Output is correct
2 Correct 244 ms 33056 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 35988 KB Output is correct
2 Correct 209 ms 35912 KB Output is correct