# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
197783 |
2020-01-23T05:22:26 Z |
Lightning |
Strah (COCI18_strah) |
C++14 |
|
159 ms |
4344 KB |
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pii;
//#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll
const int N = 2e5 + 5;
const int INF = 1e9 + 5;
int n, m, l[N], r[N];
ll ans, h[N];
ll sum(ll x) {
return (x * (x + 1)) / 2;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
string str;
cin >> str;
str = "#" + str;
for(int j = 1; j <= m; ++j) {
if(str[j] == '.') ++h[j];
else h[j] = 0;
// cout << h[j] <<' ';
}
//cout << '\n';
vector <int> st;
for(int j = 1; j <= m; ++j) {
while(sz(st) && h[st.back()] >= h[j])
st.ppb();
if(!sz(st)) l[j] = 0;
else l[j] = st.back();
st.pb(j);
}
st.clear();
for(int j = m; j >= 1; --j) {
while(sz(st) && h[st.back()] > h[j])
st.ppb();
if(!sz(st)) r[j] = m + 1;
else r[j] = st.back();
st.pb(j);
}
for(int j = 1; j <= m; ++j) {
//cout << l[j] + 1 << r[j] - 1 <<' ';
ll cntL = j - l[j];
ll cntR = r[j] - j;
ans += sum(h[j]) * (cntR * sum(cntL) + cntL * sum(cntR) - cntL * cntR);
}
//cout << '\n';
}
cout << ans;
return 0;
}
/*
If you only do what you can do,
You will never be more than you are now!
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
380 KB |
Output is correct |
2 |
Correct |
6 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
1468 KB |
Output is correct |
2 |
Correct |
94 ms |
2716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
2780 KB |
Output is correct |
2 |
Correct |
145 ms |
4028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
1956 KB |
Output is correct |
2 |
Correct |
102 ms |
2908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
772 KB |
Output is correct |
2 |
Correct |
91 ms |
3292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
4272 KB |
Output is correct |
2 |
Correct |
159 ms |
4344 KB |
Output is correct |