oj.uz

Submission #161326

# Submission time Handle Problem Language Result Execution time Memory
161326 2019-11-01T20:21:36 Z sans Strah (COCI18_strah) C++14
44 / 110
 1000 ms 83368 KB 
#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.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2296 KB Output is correct
2 Correct 214 ms 2172 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2288 KB Output is correct
2 Correct 220 ms 2296 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 791 ms 22104 KB Output is correct
2 Execution timed out 1080 ms 49912 KB Time limit exceeded

Subtask #7
0 / 11.0

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

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 6136 KB Output is correct
2 Execution timed out 1067 ms 61308 KB Time limit exceeded

Subtask #10
0 / 11.0

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