oj.uz

Submission #228189

# Submission time Handle Problem Language Result Execution time Memory
228189 2020-04-30T07:31:23 Z VEGAnn Strah (COCI18_strah) C++14
55 / 110
 64 ms 4600 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 1010;
stack<pii> st;
char c[N][N];
int down[N][N], n, m;
ll ans = 0;

ll arith(ll x){
    return x * (x + 1ll) / 2ll;
}

ll seg_arith(ll l, ll r){
    return arith(r) - arith(l - 1);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        cin >> c[i][j];

    for (int j = 1; j <= m; j++){
        down[n + 1][j] = 0;

        for (int i = n; i > 0; i--)
            if (c[i][j] == '#')
                down[i][j] = 0;
            else down[i][j] = down[i + 1][j] + 1;
    }

    for (int i = 1; i <= n; i++){
        while (sz(st)) st.pop();

        ll sm = 0, real_sm = 0;

        for (int j = m; j > 0; j--){
            pii cr = MP(down[i][j], j);

            while (sz(st) && st.top() > cr){
                pii dl = st.top(); st.pop();
                int lf = dl.sd;
                int rt = m;

                if (sz(st))
                    rt = st.top().sd - 1;

                real_sm -= seg_arith(lf - j + 1, rt - j + 1) * arith(dl.ft);
                real_sm += seg_arith(lf - j + 1, rt - j + 1) * arith(cr.ft);
                sm -= (rt - lf + 1) * arith(dl.ft);
                sm += (rt - lf + 1) * arith(cr.ft);
            }

            st.push(cr);
            sm += arith(down[i][j]);
            real_sm += arith(down[i][j]);

            ans += real_sm;
            real_sm += sm;
        }
    }

    cout << ans;

    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1920 KB Output is correct
2 Correct 8 ms 1792 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1792 KB Output is correct
2 Correct 9 ms 1920 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1920 KB Output is correct
2 Correct 9 ms 1792 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 4480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -