Submission #313528

#	Time	Username	Problem	Language	Result	Execution time	Memory
313528		balbit	Strah (COCI18_strah)	C++14	88 / 110	1083 ms	12112 KiB

strah

#include <bits/stdc++.h>
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;
}

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;
        for (int j = 0; j<m; ++j) {
            if (!at[j].empty() && at[j].front() < i) at[j].pop();
            if (!at[j].empty())
                hi.pb({at[j].front(), j});
        }
        int prv = i;
        ll now = C(m);
        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
..#.
#...
...#
*/

• 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: 0 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11