oj.uz

Submission #228190

# Submission time Handle Problem Language Result Execution time Memory
228190 2020-04-30T07:31:55 Z VEGAnn Strah (COCI18_strah) C++14
110 / 110
 215 ms 23928 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 = 2010;
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 4 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 2560 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8652 KB Output is correct
2 Correct 130 ms 17528 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 13432 KB Output is correct
2 Correct 193 ms 23100 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8704 KB Output is correct
2 Correct 137 ms 18748 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12288 KB Output is correct
2 Correct 154 ms 21756 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 20216 KB Output is correct
2 Correct 215 ms 23928 KB Output is correct