Submission #1189466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189466		12345678	Bob (COCI14_bob)	C++20	120 / 120	72 ms	16116 KiB

bob

#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

#define ll long long

struct info
{
    ll l, r, h;
    info(ll l, ll r, ll h): l(l), r(r), h(h){}
};

ll n, m, a[nx][nx], r[nx][nx], lst, res, cur;
stack<info> s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n ;i++) for (int j=1; j<=m; j++) cin>>a[i][j];
    for (int i=1; i<=n; i++)
    {
        for (int j=m; j>=1; j--)
        {
            if (a[i][j]==a[i][j+1]) r[i][j]=r[i][j+1]+1;
            else r[i][j]=1;
        }
    }
    for (int j=1; j<=m; j++)
    {
        for (int i=1; i<=n; i++)
        {
            if (a[i][j]!=a[i-1][j])
            {
                cur=0;
                lst=i-1;
                while (!s.empty()) s.pop();
            }
            while (!s.empty()&&s.top().h>=r[i][j]) cur-=(s.top().r-s.top().l+1)*s.top().h, s.pop();
            if (s.empty()) s.push(info(lst+1, i, r[i][j])), cur+=(i-lst)*r[i][j];
            else cur+=(i-s.top().r)*r[i][j], s.push(info(s.top().r+1, i, r[i][j]));
            //cout<<"Debug "<<i<<' '<<j<<' '<<cur<<'\n';
            res+=cur;
        }
    }
    cout<<res;
}

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