Submission #313533

#	Time	Username	Problem	Language	Result	Execution time	Memory
313533		balbit	Strah (COCI18_strah)	C++14	110 / 110	306 ms	8312 KiB

strah

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

#define ll long long
//#define int ll
#define pii pair<int, int>
#define f first
#define s second

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0)
#define endl '\n'
#endif // BALBIT

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

const int maxn = 2005;
queue<int> at[maxn];

inline ll C(ll x) {
    return ((x * (2*x+1) * (x+1)) / 6 + (x * (x+1)) / 2)/2;
}

inline ll S(ll a, ll b) {
    return (a+b) * (b-a+1) / 2;
}

vector<int> qh[maxn];

signed main(){
    IOS();
    bug(C(1), C(2), C(3));
    bug(1,2);
    int n,m; cin>>n>>m;
    for (int i = 0; i<n; ++i) {
        for (int j = 0; j<m; ++j) {
            char c; cin>>c;
            if (c == '#') {
                at[j].push(i);
            }
        }
    }
    ll re = 0;
    for (int i = 0; i<n; ++i) {
        set<int> s; s.insert(-1); s.insert(m);
        vector<pii> hi;

        vector<int> H(m+1, -1), L(m+1,-1), R(m+1,-1);
        vector<pii> stk = {{-1,-100}}; // position, height
        for (int j = 0; j<n; ++j) qh[j].clear();
        for (int j = 0; j<=m; ++j) {
            if (!at[j].empty() && at[j].front() < i) at[j].pop();
            if (!at[j].empty() || j == m) {
//                hi.pb({at[j].front(), j});
                if (j != m)
                    H[j] = at[j].front(), qh[H[j]] .pb (j);
                else H[j] = -100;
                while (stk.back().s > H[j]) {
                    R[stk.back().f] = j;
                    stk.pop_back();
                }
                L[j] = stk.back().f;
                stk.pb({j, H[j]});
            }
        }

        int prv = i;
        ll now = C(m);
        for (int j = i; j<n; ++j) {
            for (int x : qh[j]) {
                bug(x,L[x],R[x]);
                now -= C(R[x] - L[x] - 1);
                now += C(x-L[x]-1) + C(R[x]-x-1);
            }
            re += now * (j-i+1);
        }
//        sort(ALL(hi));
//        for (pii & p : hi) {
//            re += S(prv - i+1, p.f  - i) * now;
//            bug(re, S(prv - i+1, p.f  - i) , now);
//            auto r = s.upper_bound(p.s);
//            auto l = prev(r);
//            bug(*l,p.s,*r);
//            now -= C(*r-*l-1);
//            now += C(p.s - *l - 1) + C(*r - p.s - 1);
//            prv = p.f;
//            s.insert(p.s);
//        }
////        bug(m, prv);
//        re += S( prv - i +1 , n - i ) * now;
    }
    cout<<re<<endl;
}
/*
3 4
..#.
#...
...#
*/

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:76:13: warning: unused variable 'prv' [-Wunused-variable]
   76 |         int prv = i;
      |             ^~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11