oj.uz

Submission #219033

# Submission time Handle Problem Language Result Execution time Memory
219033 2020-04-03T12:35:19 Z brcode Strah (COCI18_strah) C++14
55 / 110
 1000 ms 53068 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2010;
pair<long long,long long> seg[4*MAXN];
long long precalc[MAXN];
long long grid[MAXN][MAXN];
long long h[MAXN][MAXN];
long long calc(long long a,long long b){
   // b--;
    return (a*(a+1)/2)-(b*(b+1)/2);
}
long long ans;
long long n,m;
void upd(long long curr,long long l,long long r,long long pos,long long val){
    if(l==r){
        seg[curr] = make_pair(val,l);
        return;
    }
    long long mid = (l+r)/2;
    if(pos<=mid){
        upd(2*curr,l,mid,pos,val);
    }else{
        upd(2*curr+1,mid+1,r,pos,val);
    }
    seg[curr] = min(seg[2*curr],seg[2*curr+1]);
}
pair<long long,long long> query(long long curr,long long l,long long r,long long tl,long long tr){
    if(l>tr||r<tl){
        return make_pair(1e9,1e9);
    }
    if(tl<=l && r<=tr){
        return seg[curr];
    }
    long long mid = (l+r)/2;
    return min(query(2*curr,l,mid,tl,tr),query(2*curr+1,mid+1,r,tl,tr));
}
void solve(long long l,long long r,long long last){
    if(r<l){
        return;
    }
    
    long long hold = query(1,1,m,l,r).first;
    //cout<<l<<" "<<r<<" "<<hold<<endl;
    ans+=(precalc[r-l+1]*calc(hold,last));
   // cout<<l<<" "<<r<<" "<<last<<" "<<hold<<" "<<calc(hold,last)<<endl;
    long long pos = query(1,1,m,l,r).second;
    
    solve(l,pos-1,hold);
    solve(pos+1,r,hold);
}
int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=m;j++){
            char x;
            cin>>x;
            if(x== '.'){
                grid[i][j] = 1;
                
            }else{
                grid[i][j] = 0;
            }
            //cout<<grid[i][j]<<endl;
        }
    }
    for(long long i=1;i<=max(n,m);i++){
        for(long long j=1;j<=i;j++){
            precalc[i]+=j*(i-j+1);
        }
    }
    for(long long i=1;i<=n;i++){
      //  cout<<ans<<endl;
        for(long long j=1;j<=m;j++){
            if(grid[i][j] == 1){
                h[i][j] = h[i-1][j]+1;
            }else{
                h[i][j] = 0;
            }
            //cout<<i<<" "<<j<<" "<<h[i][j]<<endl;
        }
        for(long long j=1;j<=m;j++){
            upd(1,1,m,j,h[i][j]);
        }
        solve(1,m,0);
    }
    cout<<ans<<endl;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 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 5 ms 384 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4216 KB Output is correct
2 Correct 43 ms 4220 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4216 KB Output is correct
2 Correct 44 ms 4216 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4252 KB Output is correct
2 Correct 45 ms 4216 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 24500 KB Output is correct
2 Execution timed out 1092 ms 48072 KB Time limit exceeded

Subtask #7
0 / 11.0

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

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 28920 KB Output is correct
2 Execution timed out 1096 ms 50040 KB Time limit exceeded

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 19448 KB Output is correct
2 Execution timed out 1052 ms 53068 KB Time limit exceeded

Subtask #10
0 / 11.0

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