oj.uz

Submission #320234

# Submission time Handle Problem Language Result Execution time Memory
320234 2020-11-08T05:40:57 Z monus1042 Strah (COCI18_strah) C++17
88 / 110
 132 ms 8292 KB 
// NK
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define psf push_front
#define pof pop_front
#define mkp make_pair
#define mkt make_tuple
#define all(x) x.begin(), x.end()
#define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr)

const int MAXS = 2003;
char ma[MAXS][MAXS];
ll triacc[MAXS], tri[MAXS];
int helper[MAXS];
int n,m;

ll f(ll x){
	return x*(x+1) / 2ll;
}

void solve(){
	cin>>n>>m;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			cin>>ma[i][j];

	for (ll i=1; i<=m; i++) triacc[i] = triacc[i-1] + i*(i+1) / 2ll, tri[i] = tri[i-1] + i;


	ll ans = 0;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			if (ma[i][j] == '.'){
				helper[j]++;
			}else helper[j] = 0;
		}

		stack<pair<int,ll>> st; // elem, counter
		st.push(mkp(0,0));
		for (int j=1; j<=m; j++){
			//cout<<helper[j];
			ll aux = 0;
			while (st.top().first > helper[j]){
				aux = st.top().second;
				int h = st.top().first;
				st.pop();
				int bh = st.top().first;

				ll diff = tri[h];
				int maxi = max(bh, helper[j]);
				diff -= tri[maxi];
				ll tmp = diff * (triacc[aux]);
				ans = ans + tmp;

				st.top().second += aux;
			}
			if (st.top().first < helper[j]){
				st.top().second -= aux;
				st.push(mkp(helper[j], aux+1));
			}else{
				st.top().second++;
			}
		}
		//pop all:
		ll aux = 0;
		while(st.top().first > 0){
			aux = st.top().second;
			int h = st.top().first;
			st.pop();
			int bh = st.top().first;

			ll diff = tri[h];
			int maxi = bh;
			diff -= tri[maxi];
			ll tmp = diff * (triacc[aux]);
			ans = ans + tmp;

			st.top().second += aux;
		}
		//cout<<'\n';
	}
	cout<<ans<<'\n';
}

int main(){
	Bolivia_is_nice;
	int t = 1; //cin>>t;
	while(t--)
	solve();
	
    return 0;
}
/*
  ~/.emacs
*/

Compilation message

strah.cpp: In function 'void solve()':
strah.cpp:36:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
   36 |  for (ll i=1; i<=m; i++) triacc[i] = triacc[i-1] + i*(i+1) / 2ll, tri[i] = tri[i-1] + i;
      |               ~^~~

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 492 KB Output isn't correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 4 ms 1004 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1004 KB Output is correct
2 Correct 5 ms 1132 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3052 KB Output is correct
2 Correct 83 ms 5860 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 5476 KB Output is correct
2 Correct 125 ms 7908 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3556 KB Output is correct
2 Correct 94 ms 6244 KB Output is correct

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4204 KB Output is correct
2 Incorrect 101 ms 6884 KB Output isn't correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 8168 KB Output is correct
2 Correct 132 ms 8292 KB Output is correct