Submission #219034

#	Time	Username	Problem	Language	Result	Execution time	Memory
219034		brcode	Strah (COCI18_strah)	C++14	66 / 110	1097 ms	57592 KiB

strah

#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(){
    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[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<<"\n";
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11