Submission #256802

#TimeUsernameProblemLanguageResultExecution timeMemory
256802PankinStrah (COCI18_strah)C++14
110 / 110
172 ms40056 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> /* #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC optimize("-O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") */ #define mp make_pair #define ll long long #define ld long double #define pb push_back #define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define fs first #define sc second #define getfiles ifstream cin("input.txt"); ofstream cout("output.txt"); #define endl '\n' #define pii pair<ll, ll> const ll INF = 2000000005; const ll BIG_INF = 2000000000000000005; const ll mod = 1000000007; const ll P = 31; const ld PI = 3.141592653589793238462643; const double eps = 1e-9; using namespace std; using namespace __gnu_pbds; bool valid(ll x, ll y, ll n, ll m) { return x >= 0 && y >= 0 && x < n && y < m; } mt19937 rng(1999999973); typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const ll N = 2005; ll n, m, nxt_r[N][N], ans = 0; string s[N]; struct seg { ll l, r, mn; seg(ll l, ll r, ll mn) { this->l = l; this->r = r; this->mn = mn; } seg() { l = -1, r = -1, mn = 0; } }; inline ll ariphm(ll l, ll r) { if (l > r) return 0; return (l + r) * (r - l + 1) / 2; } signed main() { fast_io; cin >> n >> m; for (ll i = 0; i < n; i++) cin >> s[i]; for (ll i = 0; i < n; i++) { nxt_r[i][m - 1] = s[i][m - 1] != '#'; for (ll j = m - 2; j >= 0; j--) { nxt_r[i][j] = nxt_r[i][j + 1] + 1; if (s[i][j] == '#') nxt_r[i][j] = 0; } } for (ll j = 0; j < m; j++) { vector<seg> st(1, seg()); ll sum1 = 0, sum2 = 0; for (ll i = 0; i < n; i++) { while(st.back().mn > nxt_r[i][j]) { sum1 -= ariphm(st.back().l, st.back().r) * ariphm(1, st.back().mn); sum2 -= ariphm(1, st.back().mn) * (st.back().r - st.back().l + 1); st.pop_back(); } st.pb(seg(st.back().r + 1, i, nxt_r[i][j])); sum1 += ariphm(st.back().l, st.back().r) * ariphm(1, st.back().mn); sum2 += ariphm(1, st.back().mn) * (st.back().r - st.back().l + 1); ans += sum2 * (i + 1) - sum1; } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...