Submission #750685

#	Time	Username	Problem	Language	Result	Execution time	Memory
750685		bgnbvnbv	Strah (COCI18_strah)	C++14	110 / 110	178 ms	4204 KiB

strah

#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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11