oj.uz

Submission #82294

# Submission time Handle Problem Language Result Execution time Memory
82294 2018-10-29T19:54:54 Z Milki Strah (COCI18_strah) C++14
110 / 110
 745 ms 84524 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){
    if(l > r) return;
    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
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9832 KB Output is correct
2 Correct 24 ms 9832 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9832 KB Output is correct
2 Correct 24 ms 9832 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9964 KB Output is correct
2 Correct 24 ms 9964 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 35668 KB Output is correct
2 Correct 449 ms 64032 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 64032 KB Output is correct
2 Correct 690 ms 81772 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 81772 KB Output is correct
2 Correct 486 ms 81772 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 81772 KB Output is correct
2 Correct 550 ms 81772 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 84524 KB Output is correct
2 Correct 745 ms 84524 KB Output is correct