oj.uz

Submission #756625

# Submission time Handle Problem Language Result Execution time Memory
756625 2023-06-12T02:25:55 Z Pring Strah (COCI18_strah) C++14
110 / 110
 781 ms 4856 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> pii;

const int MXN = 2005;
int n, m, a[MXN], ans;
string s[MXN];

inline int TRI(int x) {
    return x * (x + 1) / 2;
}

struct SMG {
    int n, tri[MXN * 4], big[MXN * 4], sum[MXN * 4], tag[MXN * 4];
    void init() {
        fill(big, big + MXN * 4, LLONG_MAX);
    }
    void clear() {
        fill(tri, tri + n * 4, 0);
        fill(big, big + n * 4, LLONG_MAX);
        fill(sum, sum + n * 4, 0);
        fill(tag, tag + n * 4, 0);
    }
    void add_tag(int id, int l, int r, int _tag) {
        tri[id] = _tag * (r - l);
        big[id] = _tag;
        sum[id] = _tag * (TRI(r - 1) - TRI(l - 1));
        tag[id] = _tag;
    }
    void push(int id, int l, int r) {
        if (tag[id] == 0) return;
        int mid = (l + r) >> 1;
        add_tag(id * 2 + 1, l, mid, tag[id]);
        add_tag(id * 2 + 2, mid, r, tag[id]);
        tag[id] = 0;
    }
    void pull(int id, int l, int r) {
        tri[id] = tri[id * 2 + 1] + tri[id * 2 + 2];
        big[id] = max(big[id * 2 + 1], big[id * 2 + 2]);
        sum[id] = sum[id * 2 + 1] + sum[id * 2 + 2];
    }
    void modify(int id, int l, int r, int _l, int _r, int _val) {
        if (_r <= l || r <= _l) return;
        if (_l <= l && r <= _r) {
            add_tag(id, l, r, _val);
            return;
        }
        push(id, l, r);
        int mid = (l + r) >> 1;
        modify(id * 2 + 1, l, mid, _l, _r, _val);
        modify(id * 2 + 2, mid, r, _l, _r, _val);
        pull(id, l, r);
    }
    // int query(int id, int l, int r, int _l, int _r) {
    //     if (_r <= l || r <= _l) return 0;
    //     if (_l <= l && r <= _r) return sum[id];
    //     push(id, l, r);
    //     int mid = (l + r) >> 1;
    //     return query(id * 2 + 1, l, mid, _l, _r) + query(id * 2 + 2, mid, r, _l, _r);
    // }
    int BSH(int x) {
        int id = 0, l = 0, r = n;
        while (l + 1 < r) {
            if (big[id * 2 + 1] <= x) {
                id = id * 2 + 2;
                l = (l + r) >> 1;
            } else {
                id = id * 2 + 1;
                r = (l + r) >> 1;
            }
        }
        return l;
    }
} smg;

void solve(int id, int l, int r) {
    // cout << "solve " << id << ' ' << l << ' ' << r << endl;
    smg.n = r - l;
    for (int i = 0; i < r - l; i++) {
        int x = smg.BSH(TRI(a[i + l]));
        // cout << "x " << x << endl;
        smg.modify(0, 0, smg.n, x, i + 1, TRI(a[i + l]));
        // ans += smg.query(0, 0, smg.n, 0, i + 1);
        ans += smg.tri[0] * (i + 1) - smg.sum[0];
        // cout << "ans " << ans << endl;
    }
    smg.clear();
}

void SOLVE(int id) {
    int pre = -1;
    for (int i = 0; i < m; i++) {
        if (s[id][i] == '.') continue;
        solve(id, pre + 1, i);
        pre = i;
    }
    solve(id, pre + 1, m);
}

void UPDATE(int id) {
    for (int i = 0; i < m; i++) {
        if (s[id][i] == '.') a[i]++;
        else a[i] = 1;
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n >> m;
    fill(a, a + m, 1);
    for (int i = 0; i < n; i++) cin >> s[i];
    smg.init();
    for (int i = 0; i < n; i++) {
        SOLVE(i);
        UPDATE(i);
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 8 ms 468 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 10 ms 468 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 588 KB Output is correct
2 Correct 13 ms 468 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1568 KB Output is correct
2 Correct 230 ms 2988 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 3060 KB Output is correct
2 Correct 445 ms 4328 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 2180 KB Output is correct
2 Correct 380 ms 3188 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 724 KB Output is correct
2 Correct 544 ms 3688 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 4856 KB Output is correct
2 Correct 202 ms 4684 KB Output is correct