oj.uz

Submission #82295

# Submission time Handle Problem Language Result Execution time Memory
82295 2018-10-29T20:03:26 Z Milki Strah (COCI18_strah) C++14
0 / 110
 290 ms 263168 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 2e3 + 5, INF = 1e9, off = 1 << 11;

int n, m;
char c[MAXN][MAXN];
int down[MAXN][MAXN];

struct Tournament{
    point t[2 * off];

    point merge(point a, point b){
        if(a.first > b.first) swap(a, b);
        if(a.first == b.first) return point(a.first, min(a.second, b.second));
        return a;
    }

    void add(int x, int val){
        t[x + off] = point(val, x);
    }

    void build(){
        for(int i = off - 1; i > 0; --i)
            t[i] = merge(t[i * 2], t[i * 2 + 1]);
    }

    point get(int x, int lo, int hi, int a, int b){
        if(hi <= a || lo >= b) return point(INF, -1);
        if(lo >= a && hi <= b) return t[x];

        int mid = (lo + hi) >> 1;
        point X = get(x * 2, lo, mid, a, b);
        point Y = get(x * 2 + 1, mid, hi, a, b);
        return merge(X, Y);
    }
} T[MAXN];

ll sol;

ll calc(ll x, ll y){
    return ((y * (y + 1)) / 2) * (x * (x + 1) * (x + 2) / 6);
}

void solve(int l, int r, int curr, int last){
    point x = T[curr].get(1, 0, off, l, r + 1);
    ll add = calc(r - l + 1, last);
    sol += calc(r - l + 1, x.first) - add;

    if(l == r) return;
    solve(l, x.second - 1, curr, x.first);
    solve(x.second + 1, r, curr, x.first);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    REP(i, n)
        REP(j, m)
            cin >> c[i][j];

    for(int i = n - 1; i >= 0; --i)
        REP(j, m){
            if(c[i][j] == '#')
                down[i][j] = 0;
            else
                down[i][j] = down[i + 1][j] + 1;
            T[i].add(j, down[i][j]);
        }
    REP(i, n)
        T[i].build();

    REP(i, n){
        solve(0, m - 1, i, 0);
    }

    cout << sol;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 228 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 216 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 218 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 255 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 283 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 245 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 290 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -