oj.uz

Submission #504124

# Submission time Handle Problem Language Result Execution time Memory
504124 2022-01-09T21:24:52 Z tabr Pyramid Base (IOI08_pyramid_base) C++17
80 / 100
 3453 ms 90020 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

namespace solve1 {
struct segtree {
    using T = int;
    using F = int;

    T e() {
        return (int) 2e9;
    }

    F id() {
        return 0;
    }

    T op(T a, T b) {
        return min(a, b);
    }

    T mapping(F f, T x) {
        return f + x;
    }

    F composition(F f, F g) {
        return f + g;
    }

    int n;
    vector<T> node;
    vector<F> lazy;

    segtree() : segtree(0) {}
    segtree(int _n) {
        if (_n <= 1) {
            n = _n;
        } else {
            n = 1 << (32 - __builtin_clz(_n - 1));
        }
        node.resize(2 * n, e());
        lazy.resize(n, id());
    }
    segtree(vector<T> v) {
        if ((int) v.size() <= 1) {
            n = (int) v.size();
        } else {
            n = 1 << (32 - __builtin_clz((int) v.size() - 1));
        }
        node.resize(2 * n, e());
        lazy.resize(n, id());
        for (int i = 0; i < (int) v.size(); i++) {
            node[i + n] = v[i];
        }
        for (int i = n - 1; i > 0; i--) {
            node[i] = op(node[i * 2], node[i * 2 + 1]);
        }
    }

    void eval(int k) {
        node[2 * k] = mapping(lazy[k], node[2 * k]);
        node[2 * k + 1] = mapping(lazy[k], node[2 * k + 1]);
        if (2 * k < n) {
            lazy[2 * k] = composition(lazy[k], lazy[2 * k]);
            lazy[2 * k + 1] = composition(lazy[k], lazy[2 * k + 1]);
        }
        lazy[k] = id();
    }

    void update(int x, int y, F v, int k, int l, int r) {
        if (y <= l || r <= x) {
            return;
        }
        if (x <= l && r <= y) {
            node[k] = mapping(v, node[k]);
            if (k < n) {
                lazy[k] = composition(v, lazy[k]);
            }
        } else {
            eval(k);
            update(x, y, v, 2 * k, l, (l + r) / 2);
            update(x, y, v, 2 * k + 1, (l + r) / 2, r);
            node[k] = op(node[2 * k], node[2 * k + 1]);
        }
    }

    T get(int x, int y, int k, int l, int r) {
        if (y <= l || r <= x) {
            return e();
        }
        if (x <= l && r <= y) {
            return node[k];
        }
        eval(k);
        T vl = get(x, y, 2 * k, l, (l + r) / 2);
        T vr = get(x, y, 2 * k + 1, (l + r) / 2, r);
        return op(vl, vr);
    }

    void update(int x, int y, F v) {
        update(x, y, v, 1, 0, n);
    }

    T get(int x, int y) {
        return get(x, y, 1, 0, n);
    }

    T get(int x) {
        return get(x, x + 1, 1, 0, n);
    }
};

void solve(int h, int w, int d, int n, vector<tuple<int, int, int, int>> a, vector<tuple<int, int, int, int>> b) {
    int hi = min(w, h) + 1;
    int lo = 0;
    while (hi - lo > 1) {
        int mid = (hi + lo) / 2;
        segtree seg = segtree(vector<int>(w, 0));
        int aid = 0;
        int bid = 0;
        int ok = 0;
        for (int i = 0; i < h - mid + 1; i++) {
            while (bid < n && get<0>(b[bid]) <= i) {
                auto [x2, y1, y2, c] = b[bid];
                y1 = max(0, y1 - mid + 1);
                seg.update(y1, y2, -c);
                bid++;
            }
            while (aid < n && get<0>(a[aid]) - mid + 1 <= i) {
                auto [x1, y1, y2, c] = a[aid];
                y1 = max(0, y1 - mid + 1);
                seg.update(y1, y2, c);
                aid++;
            }
            if (seg.get(0, w - mid + 1) <= d) {
                ok = 1;
                break;
            }
        }
        if (ok) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    cout << lo << '\n';
}
}  // namespace solve1

namespace solve0 {
struct segtree {
    using T = array<int, 5>;
    using F = int;

    T e() {
        return array<int, 5>{(int) 2e9, 0, 0, 0, -1};
    }

    F id() {
        return 0;
    }

    T op(T a, T b) {
        if (a[4] == -1) {
            return b;
        } else if (b[4] == -1) {
            return a;
        }
        if (a[0] < b[0]) {
            a[2] = 0;
            a[4] += b[4];
            return a;
        } else if (a[0] > b[0]) {
            b[1] = 0;
            b[4] += a[4];
            return b;
        }
        a[3] = max({a[3], b[3], a[2] + b[1]});
        if (a[1] == a[4] && b[1] == b[4]) {
            a[1] = a[2] = a[1] + b[1];
        } else if (a[1] == a[4]) {
            a[1] += b[1];
            a[2] = b[2];
        } else if (b[1] == b[4]) {
            a[2] = a[2] + b[2];
        } else {
            a[2] = b[2];
        }
        a[4] += b[4];
        return a;
    }

    T mapping(F f, T x) {
        x[0] += f;
        return x;
    }

    F composition(F f, F g) {
        return f + g;
    }

    int n;
    vector<T> node;
    vector<F> lazy;

    segtree() : segtree(0) {}
    segtree(int _n) {
        if (_n <= 1) {
            n = _n;
        } else {
            n = 1 << (32 - __builtin_clz(_n - 1));
        }
        node.resize(2 * n, e());
        lazy.resize(n, id());
    }
    segtree(vector<T> v) {
        if ((int) v.size() <= 1) {
            n = (int) v.size();
        } else {
            n = 1 << (32 - __builtin_clz((int) v.size() - 1));
        }
        node.resize(2 * n, e());
        lazy.resize(n, id());
        for (int i = 0; i < (int) v.size(); i++) {
            node[i + n] = v[i];
        }
        for (int i = n - 1; i > 0; i--) {
            node[i] = op(node[i * 2], node[i * 2 + 1]);
        }
    }

    void eval(int k) {
        node[2 * k] = mapping(lazy[k], node[2 * k]);
        node[2 * k + 1] = mapping(lazy[k], node[2 * k + 1]);
        if (2 * k < n) {
            lazy[2 * k] = composition(lazy[k], lazy[2 * k]);
            lazy[2 * k + 1] = composition(lazy[k], lazy[2 * k + 1]);
        }
        lazy[k] = id();
    }

    void update(int x, int y, F v, int k, int l, int r) {
        if (y <= l || r <= x) {
            return;
        }
        if (x <= l && r <= y) {
            node[k] = mapping(v, node[k]);
            if (k < n) {
                lazy[k] = composition(v, lazy[k]);
            }
        } else {
            eval(k);
            update(x, y, v, 2 * k, l, (l + r) / 2);
            update(x, y, v, 2 * k + 1, (l + r) / 2, r);
            node[k] = op(node[2 * k], node[2 * k + 1]);
        }
    }

    T get(int x, int y, int k, int l, int r) {
        if (y <= l || r <= x) {
            return e();
        }
        if (x <= l && r <= y) {
            return node[k];
        }
        eval(k);
        T vl = get(x, y, 2 * k, l, (l + r) / 2);
        T vr = get(x, y, 2 * k + 1, (l + r) / 2, r);
        return op(vl, vr);
    }

    void update(int x, int y, F v) {
        update(x, y, v, 1, 0, n);
    }

    T get(int x, int y) {
        return get(x, y, 1, 0, n);
    }

    T get(int x) {
        return get(x, x + 1, 1, 0, n);
    }
};

void solve(int h, int w, int, int n, vector<tuple<int, int, int, int>> a, vector<tuple<int, int, int, int>> b) {
    int ans = 0;
    int aid = 0;
    int bid = 0;
    segtree seg = segtree(vector<array<int, 5>>(w, {0, 1, 1, 1, 1}));
    for (int beg = 0, end = 0; beg <= h; beg++) {
        while (bid < n && get<0>(b[bid]) <= beg) {
            seg.update(get<1>(b[bid]), get<2>(b[bid]), -1);
            bid++;
        }
        while (seg.node[1][0] == 0 && end - beg <= seg.node[1][3] && end <= h) {
            debug(beg, end, seg.node[1]);
            ans = max(ans, end - beg);
            while (aid < n && get<0>(a[aid]) <= end) {
                seg.update(get<1>(a[aid]), get<2>(a[aid]), 1);
                aid++;
            }
            end++;
        }
    }
    cout << ans << '\n';
}
}  // namespace solve0

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    int d;
    cin >> d;
    int n;
    cin >> n;
    vector<tuple<int, int, int, int>> a(n), b(n);
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        x1--, y1--;
        a[i] = make_tuple(x1, y1, y2, c);
        b[i] = make_tuple(x2, y1, y2, c);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    if (d == 0) {
        solve0::solve(h, w, d, n, a, b);
    } else {
        solve1::solve(h, w, d, n, a, b);
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7884 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 65100 KB Output is correct
2 Correct 48 ms 64972 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 65076 KB Output is correct
2 Correct 47 ms 64996 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 868 KB Output is correct
2 Correct 60 ms 884 KB Output is correct
3 Correct 48 ms 864 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 3188 KB Output is correct
2 Correct 427 ms 3196 KB Output is correct
3 Correct 402 ms 3172 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 17808 KB Output is correct
2 Correct 59 ms 1568 KB Output is correct
3 Correct 169 ms 17772 KB Output is correct
4 Correct 1499 ms 17796 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1508 ms 18220 KB Output is correct
2 Correct 3157 ms 18104 KB Output is correct
3 Correct 696 ms 18124 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 18420 KB Output is correct
2 Correct 3453 ms 18424 KB Output is correct
3 Correct 3129 ms 18424 KB Output is correct
4 Correct 3437 ms 18416 KB Output is correct
5 Correct 3395 ms 18424 KB Output is correct
6 Correct 529 ms 18432 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 77480 KB Output is correct
2 Correct 218 ms 20396 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 83808 KB Output is correct
2 Incorrect 467 ms 83808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 89968 KB Output is correct
2 Correct 657 ms 90012 KB Output is correct
3 Incorrect 747 ms 90020 KB Output isn't correct
4 Halted 0 ms 0 KB -