oj.uz

Submission #219047

# Submission time Handle Problem Language Result Execution time Memory
219047 2020-04-03T13:11:22 Z brcode Strah (COCI18_strah) C++14
110 / 110
 987 ms 35960 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];
long long calc(long long a,long long 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;
    }
    if(l==r){
        ans+=(calc(h[l],last));
        return;
    }
    auto hold1 = query(1,1,m,l,r);
    long long hold = hold1.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 = hold1.second;
    
    solve(l,pos-1,hold);
    solve(pos+1,r,hold);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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[j]++;
            }else{
                h[j]=0;
            }
            //cout<<i<<" "<<j<<" "<<h[i][j]<<endl;
        }
        for(long long j=1;j<=m;j++){
            upd(1,1,m,j,h[j]);
        }
        solve(1,m,0);
    }
    cout<<ans<<"\n";
}

Subtask #1
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 #2
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 #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 13056 KB Output is correct
2 Correct 586 ms 26640 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 23816 KB Output is correct
2 Correct 912 ms 34560 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 15352 KB Output is correct
2 Correct 653 ms 28356 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 10104 KB Output is correct
2 Correct 712 ms 32924 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 35960 KB Output is correct
2 Correct 987 ms 35960 KB Output is correct