Submission #161326

#	Time	Username	Problem	Language	Result	Execution time	Memory
161326		sans	Strah (COCI18_strah)	C++14	44 / 110	1080 ms	83368 KiB

strah

#include <bits/stdc++.h>
using namespace std;

#define sp ' '
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(int yy = 0; yy < YY; ++yy)

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> ii;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;

int N, M;
vector<vector<bool>> field;

vvi segtrees, uzaklik;

//Input
void input(void)
{
    cin >> N >> M;
    field.assign(N, vector<bool>(M, false));

    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            char ch; cin >> ch;
            field[i][j] = (ch == '.' ? true : false);
        }
    }
    return;
}

void build(int start, int end, int node, int s)
{
    if(start == end){ segtrees[s][node] = uzaklik[s][start]; return; }

    int mid = (start + end) / 2;

    build(start, mid, 2*node + 1, s);
    build(mid+1, end, 2*node + 2, s);

    segtrees[s][node] = min(segtrees[s][2*node+1], segtrees[s][2*node+2]);

    return;
}

int getmin(int start, int end, int node, int s, int l, int r)
{
    if(start >= l and end <= r) return segtrees[s][node];
    if(l > end or r < start) return INF;

    int mid = (start + end) / 2;

    int p1 = getmin(start, mid, 2*node+1, s, l, r);
    int p2 = getmin(mid+1, end, 2*node+2, s, l, r);

    return min(p1, p2);
}

int solve(void)
{
    ll sum = 0;
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            for(int k = j; k < M; ++k)
            {
                int m = getmin(0, M-1, 0, i, j, k);
                if(m == 0) break;
                int r = k - j + 1;
                sum += ((m*(m+1))/2)*r;
            }
        }
    }
    return sum;
}

int main(int argc, char **argv)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();

    
    uzaklik.assign(N, vi(M, -1));
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            if(!field[i][j]){ uzaklik[i][j] = 0; continue; }
            if(i and field[i-1][j]){ uzaklik[i][j] = uzaklik[i-1][j] - 1; continue; }

            for(int k = i+1; k < N; ++k)
                if(!field[k][j]){ uzaklik[i][j] = k-i; break; }
            if(uzaklik[i][j] == -1) uzaklik[i][j] = N - i;
        }
    }

    segtrees.assign(N, vi(4*M, 0));
    for(int i = 0; i < N; ++i) build(0, M-1, 0, i);

    cout << solve() << endl;

    return 0;
}

//cikisir

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