oj.uz

Submission #1091801

# Submission time Handle Problem Language Result Execution time Memory
1091801 2024-09-22T07:35:46 Z hahahaha Strah (COCI18_strah) C++17
110 / 110
 105 ms 4176 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 344 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1368 KB Output is correct
2 Correct 59 ms 2748 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2636 KB Output is correct
2 Correct 90 ms 4040 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1864 KB Output is correct
2 Correct 64 ms 2896 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 56 ms 3328 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 4176 KB Output is correct
2 Correct 105 ms 4152 KB Output is correct