oj.uz

Submission #219035

# Submission time Handle Problem Language Result Execution time Memory
219035 2020-04-03T12:50:19 Z brcode Strah (COCI18_strah) C++14
88 / 110
 1000 ms 34552 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){
   // 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;
    }
    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[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 4 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 30 ms 2304 KB Output is correct
2 Correct 30 ms 2304 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2304 KB Output is correct
2 Correct 33 ms 2304 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2280 KB Output is correct
2 Correct 30 ms 2304 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 12032 KB Output is correct
2 Correct 783 ms 24312 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 21496 KB Output is correct
2 Execution timed out 1098 ms 34552 KB Time limit exceeded

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 13912 KB Output is correct
2 Correct 874 ms 25848 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9728 KB Output is correct
2 Correct 955 ms 30072 KB Output is correct

Subtask #10
0 / 11.0

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