oj.uz

Submission #101133

# Submission time Handle Problem Language Result Execution time Memory
101133 2019-03-17T00:26:33 Z Ort Strah (COCI18_strah) C++11
110 / 110
 132 ms 4344 KB 
#include<iostream>
#include<stack>
#include<vector>
#define ll long long
 
using namespace std;
 
int n, m;
vector<int> a;
ll sol = 0;

void f() {
  	stack<int> s;
  	vector<int> l(m,0), r(m,0);
  	ll x = 0;
 	for (int i=0;i<m;i++) {
   		while (!s.empty() && a[i] <= a[s.top()]) {
    		r[s.top()] = i; s.pop();
    	}
    	l[i] = s.empty() ? -1 : s.top();
    	s.push(i);
  	}
  	while(!s.empty()){
    	r[s.top()] = m;
    	s.pop();
  	}
  	for(int i=0;i<m;i++) {
  		ll b = i - l[i] - 1, c = r[i] - i - 1, e = a[i];
  		x += (b+1)*(c+1)*(e*(e+1)/2)+(e*(e+1)/2)*(c*(c+1)/2)*(b+1)+(c+1)*(e*(e+1)/2)*(b*(b+1)/2);
  	}
  	sol += x;
}
 
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	cin >> n >> m;
  	a.resize(m,0);
  	for(int i=0;i<n;i++) {
    	for(int j=0;j<m;j++) {
      		char c; cin >> c;
      		if (c == '.') a[j]++;
      		else a[j] = 0;
    	}
    	f();
  	}
  	cout << sol;
  return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 488 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 524 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1408 KB Output is correct
2 Correct 73 ms 2684 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2936 KB Output is correct
2 Correct 113 ms 3960 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1948 KB Output is correct
2 Correct 78 ms 2924 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 640 KB Output is correct
2 Correct 76 ms 3188 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 4344 KB Output is correct
2 Correct 132 ms 4216 KB Output is correct