oj.uz

Submission #750685

# Submission time Handle Problem Language Result Execution time Memory
750685 2023-05-30T06:53:20 Z bgnbvnbv Strah (COCI18_strah) C++14
110 / 110
 178 ms 4204 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m;
ll h[maxN];
ll l[maxN],r[maxN],ans=0;
ll cal(ll x)
{
    return x*(x+1)/2;
}
ll take(ll l1, ll x, ll r1)
{
    ll a1=((r1-x+1)*(x+r1+2)/2)*(x-l1+1);
    ll b1=((x-l1+1)*(l1+x)/2)*(r1-x+1);
    return a1-b1;
}
void solve()
{
    cin >>n >> m;
    char c;
    deque<int>dq;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> c;
            if(c=='#') h[j]=0;
            else h[j]++;
        }
        dq.clear();
        for(int j=1;j<=m;j++)
        {
            while(!dq.empty()&&h[j]<h[dq.back()]) dq.pop_back();
            if(dq.size()==0) l[j]=1;
            else l[j]=dq.back()+1;
            dq.pb(j);
        }
        dq.clear();
        for(int j=m;j>=1;j--)
        {
            while(!dq.empty()&&h[j]<=h[dq.back()]) dq.pop_back();
            if(dq.size()==0) r[j]=m;
            else r[j]=dq.back()-1;
            dq.pb(j);
            ans+=cal(h[j])*take(l[j],j,r[j]);
        }
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 5 ms 440 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1372 KB Output is correct
2 Correct 112 ms 2708 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 2764 KB Output is correct
2 Correct 158 ms 3948 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 1772 KB Output is correct
2 Correct 125 ms 2912 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 616 KB Output is correct
2 Correct 123 ms 3168 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 4204 KB Output is correct
2 Correct 178 ms 4204 KB Output is correct