oj.uz

Submission #219036

# Submission time Handle Problem Language Result Execution time Memory
219036 2020-04-03T12:51:48 Z brcode Strah (COCI18_strah) C++14
77 / 110
 1000 ms 16120 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2010;
pair<int,int> seg[4*MAXN];
int precalc[MAXN];
int grid[MAXN][MAXN];
int h[MAXN];
int calc(int a,int b){
   // b--;
    return (a*(a+1)/2)-(b*(b+1)/2);
}
long long ans;
int n,m;
void upd(int curr,int l,int r,int pos,int val){
    if(l==r){
        seg[curr] = make_pair(val,l);
        return;
    }
    int 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<int,int> query(int curr,int l,int r,int tl,int tr){
    if(l>tr||r<tl){
        return make_pair(1e9,1e9);
    }
    if(tl<=l && r<=tr){
        return seg[curr];
    }
    int mid = (l+r)/2;
    return min(query(2*curr,l,mid,tl,tr),query(2*curr+1,mid+1,r,tl,tr));
}
void solve(int l,int r,int last){
    if(r<l){
        return;
    }
    if(l==r){
        ans+=(calc(h[l],last));
        return;
    }
    int 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;
    int 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(int i=1;i<=n;i++){
        for(int 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(int i=1;i<=max(n,m);i++){
        for(int j=1;j<=i;j++){
            precalc[i]+=j*(i-j+1);
        }
    }
    for(int i=1;i<=n;i++){
      //  cout<<ans<<endl;
        for(int j=1;j<=m;j++){
            if(grid[i][j] == 1){
                h[j]++;
            }else{
                h[j]=0;
            }
            //cout<<i<<" "<<j<<" "<<h[i][j]<<endl;
        }
        for(int 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 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 29 ms 1920 KB Output is correct
2 Correct 30 ms 1920 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1920 KB Output is correct
2 Correct 32 ms 1920 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 7140 KB Output is correct
2 Correct 781 ms 12284 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 10872 KB Output is correct
2 Execution timed out 1092 ms 15608 KB Time limit exceeded

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 7160 KB Output is correct
2 Correct 860 ms 13156 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8704 KB Output is correct
2 Correct 968 ms 15332 KB Output is correct

Subtask #10
0 / 11.0

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