oj.uz

Submission #397422

# Submission time Handle Problem Language Result Execution time Memory
397422 2021-05-02T07:06:37 Z mewnian Bob (COCI14_bob) C++14
120 / 120
 185 ms 41540 KB 
#include <bits/stdc++.h>
#define sze(x) (ll)x.size()
#define idx(x, a) get<x>(a)
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;

const ll MAXN = 1e3 + 3;
const ll INF = 1e18 + 7;

ll a[MAXN][MAXN], h[MAXN][MAXN], l[MAXN][MAXN], cnt[MAXN][MAXN], m, n, res = 0;

int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0);
    #ifdef OFFLINE
    freopen("input.inp", "r", stdin);
    #endif
    cin >> m >> n;
    for (ll i = 1; i <= m; ++i)
    {
        for (ll j = 1; j <= n; ++j) cin >> a[i][j];
        h[i][0] = h[i][n + 1] = -INF;
    }
    fill(h[1] + 1, h[1] + n + 1, 1);
    for (ll i = 2; i <= m; ++i)
        for (ll j = 1; j <= n; ++j)
            h[i][j] = (a[i][j] == a[i - 1][j] ? h[i - 1][j] + 1 : 1);
    vector<ll> posL;
    for (ll i = 1; i <= m; ++i)
    {
    	posL.clear();
        for (ll j = 1; j <= n; ++j)
        {
            if (j == 1 || a[i][j] != a[i][j - 1]) posL = {j - 1};
            else
            while (a[i][j] == a[i][posL.back()] && h[i][j] <= h[i][posL.back()])
            {
                //cnt[i][j] += (j - posL.back()) * h[i][j];
                posL.pop_back();
            }
            l[i][j] = posL.back();
            posL.push_back(j);
            cnt[i][j] += (j - l[i][j]) * h[i][j];
            if (a[i][l[i][j]] == a[i][j]) cnt[i][j] += cnt[i][l[i][j]];
            //cerr << cnt[i][j] << ' ';
            res += cnt[i][j];
        }
        //cerr << endl;
    }
    cout << res;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16512 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16976 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 17160 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17092 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 38316 KB Output is correct
2 Correct 89 ms 33580 KB Output is correct
3 Correct 92 ms 33656 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 41540 KB Output is correct
2 Correct 94 ms 33652 KB Output is correct
3 Correct 87 ms 33560 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 41192 KB Output is correct
2 Correct 90 ms 33552 KB Output is correct
3 Correct 98 ms 33612 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 41400 KB Output is correct
2 Correct 90 ms 33584 KB Output is correct
3 Correct 87 ms 33732 KB Output is correct