oj.uz

Submission #82226

# Submission time Handle Problem Language Result Execution time Memory
82226 2018-10-29T14:28:49 Z ngot23 Bob (COCI14_bob) C++11
48 / 120
 1000 ms 48148 KB 
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=1005;
int f[N][N], m, n, a[N][N], luu[N], dem, rmq[N][12];
long long ans;

int getmin(int i, int j) {
    int leng=j-i+1;
    int logg=log2(leng);
    return min(rmq[i][logg], rmq[j-(1ll<<logg)+1][logg]);
}

void tinh() {
    rep(i, 1, dem) rmq[i][0]=luu[i];
    rep(i, 1, 10)
        for(int j=1 ; j+(1ll<<i)-1<=dem ; ++j) {
            rmq[j][i]=min(rmq[j][i-1], rmq[j+(1ll<<(i-1))][i-1]);
        }
    rep(i, 1, dem) {
        rep(val, 1, luu[i]) {
            int r=dem+1, l=i;
            while(r-l>1) {
                int mid=(r+l)>>1;
                if(getmin(i, mid)<val) r=mid;
                else l=mid;
            }
            ans+=r-i;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> m >> n;
    rep(i, 1, m)
        rep(j, 1, n) {
            cin >> a[i][j];
            f[i][j]=1;
            if(a[i-1][j]==a[i][j]) f[i][j]+=f[i-1][j];
        }

    rep(i, 1, m) {
        int ptr=1;
        a[i][n+1]=-1;
        while(ptr<=n) {
            int j=ptr;
            dem=0;
            for( ; j<=n ; ++j) {
                luu[++dem]=f[i][j];
                if(a[i][j]!=a[i][j+1]) {
                    tinh();
                    break;
                }
            }
            ptr=j+1;
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 6136 KB Time limit exceeded

Subtask #5
12.0 / 12.0

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

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 8388 KB Time limit exceeded

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 19120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 28864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 38240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 48148 KB Time limit exceeded
2 Halted 0 ms 0 KB -