oj.uz

Submission #313528

# Submission time Handle Problem Language Result Execution time Memory
313528 2020-10-16T07:53:34 Z balbit Strah (COCI18_strah) C++14
88 / 110
 1000 ms 12112 KB 
#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.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1792 KB Output is correct
2 Correct 28 ms 1664 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1792 KB Output is correct
2 Correct 29 ms 1664 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1664 KB Output is correct
2 Correct 28 ms 1664 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 3192 KB Output is correct
2 Correct 866 ms 5112 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 5448 KB Output is correct
2 Execution timed out 1083 ms 6392 KB Time limit exceeded

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 1860 KB Output is correct
2 Correct 947 ms 5372 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2168 KB Output is correct
2 Correct 938 ms 1964 KB Output is correct

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 2040 KB Output is correct
2 Execution timed out 1082 ms 12112 KB Time limit exceeded