oj.uz

Submission #1095237

# Submission time Handle Problem Language Result Execution time Memory
1095237 2024-10-01T15:40:43 Z SoMotThanhXuan Bob (COCI14_bob) C++17
120 / 120
 100 ms 18004 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e3 + 5;
int a[maxN][maxN], N, M;
namespace subtask1{
    bool check(){
        return max(N, M) <= 50;
    }
    bool ok[51][51][51][51];
    void solve(){
        int res = 0;
        for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)ok[i][j][i][j] = 1;
        for(int i = 1; i <= N; ++i){
            for(int j = 1; j <= M; ++j){
                for(int x = i + 1; x <= N; ++x){
                    if(a[i][j] == a[x][j]) ok[i][j][x][j] = ok[i][j][x - 1][j];
                }
                for(int y = j + 1; y <= M; ++y){
                    if(a[i][j] == a[i][y]) ok[i][j][i][y] = ok[i][j][i][y - 1];
                }
                for(int x = i + 1; x <= N; ++x){
                    for(int y = j + 1; y <= M; ++y){
                        if(a[x][y] == a[i][j]){
                            ok[i][j][x][y] = ok[i][j][x - 1][y] && ok[i][j][x][y - 1];
                        }
                    }
                }
            }
        }
        for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)for(int x = i; x <= N; ++x)for(int y = j; y <= M; ++y)
        if(ok[i][j][x][y]){
            ++res;
        }
        cout << res;
    }
}
namespace subtask23{
    int nxt[maxN][maxN];
    int l[maxN], r[maxN];
    int h[maxN];
    void solve(){
        for(int i = 1; i <= N; ++i){
            for(int l = 1, r = 1; l <= M;){
                while(r <= M && a[i][l] == a[i][r])++r;
                nxt[i][l] = r;
                l = r;
            }
        }
        long long res = 0;
        for(int i = 1; i <= N; ++i){
            for(int j = 1; j <= M; ++j){
                h[j] = (a[i][j] == a[i - 1][j] ? h[j] + 1 : 1);
                l[j] = r[j] = 0;
            }
            for(int j = 1; j <= M; j = nxt[i][j]){
                stack<int> st;
                for(int k = j; k < nxt[i][j]; ++k){\
                    while(!st.empty() && h[st.top()] >= h[k])st.pop();
                    if(st.empty()) l[k] = j;
                    else l[k] = st.top() + 1;
                    st.push(k);
                }
                while(!st.empty())st.pop();
                for(int k = nxt[i][j] - 1; k >= j; --k){
                    while(!st.empty() && h[st.top()] > h[k]) st.pop();
                    if(st.empty())r[k] = nxt[i][j] - 1;
                    else r[k] = st.top() - 1;
                    st.push(k);
                }
            }
            for(int j = 1; j <= M; ++j)res += 1ll * h[j] * (j - l[j] + 1) * (r[j] - j + 1);
        }
        cout << res;
    }
}
int main(){
//    freopen("s2.inp", "r", stdin);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; ++i)
    for(int j = 1; j <= M; ++j){
        cin >> a[i][j];
    }
//    if(subtask1 :: check()) return subtask1 :: solve(), 0;
    return subtask23 :: solve(), 0;
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14768 KB Output is correct
2 Correct 44 ms 10292 KB Output is correct
3 Correct 42 ms 10044 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 18004 KB Output is correct
2 Correct 46 ms 10076 KB Output is correct
3 Correct 50 ms 10068 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 17744 KB Output is correct
2 Correct 41 ms 10076 KB Output is correct
3 Correct 44 ms 10048 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 17948 KB Output is correct
2 Correct 43 ms 10068 KB Output is correct
3 Correct 41 ms 10064 KB Output is correct