oj.uz

Submission #689356

# Submission time Handle Problem Language Result Execution time Memory
689356 2023-01-28T09:40:59 Z finn__ Pyramid Base (IOI08_pyramid_base) C++17
80 / 100
 5000 ms 45444 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")

template <typename T>
class SegmentTreeMin
{
    vector<T> t, z;
    size_t l;
    T neutral;

public:
    SegmentTreeMin(size_t n, T _neutral)
    {
        neutral = _neutral;
        l = 1 << (32 - __builtin_clz(n));
        t = vector<T>(2 * l, neutral);
        z = vector<T>(2 * l, 0);

        fill(t.begin() + l, t.begin() + l + n, 0);
        for (size_t i = l - 1; i; i--)
            t[i] = min(t[2 * i], t[2 * i + 1]);
    }

private:
    void propagate(size_t k, size_t x, size_t y)
    {
        t[2 * k] += z[k];
        t[2 * k + 1] += z[k];
        z[2 * k] += z[k];
        z[2 * k + 1] += z[k];
        z[k] = 0;
    }

    void increment_r(size_t i, size_t j, T v, size_t k, size_t x, size_t y)
    {
        if (x > y || y < i || x > j)
            return;
        if (i <= x && y <= j)
        {
            t[k] += v;
            z[k] += v;
        }
        else
        {
            propagate(k, x, y);
            increment_r(i, j, v, 2 * k, x, (x + y) / 2);
            increment_r(i, j, v, 2 * k + 1, (x + y) / 2 + 1, y);
            t[k] = min(t[2 * k], t[2 * k + 1]);
        }
    }

public:
    void increment(size_t i, size_t j, T v)
    {
        increment_r(i, j, v, 1, 0, l - 1);
    }

    T get_global_min() const
    {
        return t[1];
    }
};

struct Rectangle
{
    int x1, y1, x2, y2, cost;
};

struct Event
{
    int x, y1, y2, cost;

    Event(int _x, int _y1, int _y2, int _cost)
    {
        x = _x;
        y1 = _y1;
        y2 = _y2;
        cost = _cost;
    }

    bool operator<(Event const &e) const
    {
        return x < e.x;
    }
};

bool can_place_square(
    vector<Rectangle> const &rectangles, int m, int n, int side_length, int b)
{
    vector<Event> events;

    for (Rectangle const &r : rectangles)
    {
        events.emplace_back(
            r.x1 - side_length + 1, max(r.y1 - side_length + 1, 0), r.y2, r.cost);
        events.emplace_back(
            r.x2 + 1, max(r.y1 - side_length + 1, 0), r.y2, -r.cost);
    }

    sort(events.begin(), events.end());
    SegmentTreeMin<int> tree(n - side_length + 1, INT_MAX);
    int curr_x = events[0].x;

    for (Event const &e : events)
    {
        if (curr_x > m - side_length)
            return 0;
        if (e.x != curr_x && 0 < e.x && curr_x <= m - side_length)
        {
            if (tree.get_global_min() <= b)
                return 1;
            curr_x = e.x;
        }
        tree.increment(e.y1, min(e.y2, n - side_length), e.cost);
    }

    return 0;
}

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

    unsigned m, n, b, p;
    cin >> m >> n >> b >> p;

    vector<Rectangle> rectangles(p);
    for (auto &[x1, y1, x2, y2, cost] : rectangles)
    {
        cin >> x1 >> y1 >> x2 >> y2 >> cost;
        x1--, y1--, x2--, y2--;
    }

    unsigned u = 0, v = min(m, n);
    while (u < v)
    {
        unsigned side_length = (u + v + 1) / 2;
        if (can_place_square(rectangles, m, n, side_length, b))
            u = side_length;
        else
            v = side_length - 1;
    }

    cout << u << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8532 KB Output is correct
2 Correct 158 ms 16952 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 16928 KB Output is correct
2 Correct 76 ms 8676 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 816 KB Output is correct
2 Correct 51 ms 960 KB Output is correct
3 Correct 38 ms 968 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 3768 KB Output is correct
2 Correct 249 ms 3652 KB Output is correct
3 Correct 205 ms 3656 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 10684 KB Output is correct
2 Correct 34 ms 2328 KB Output is correct
3 Correct 172 ms 18776 KB Output is correct
4 Correct 462 ms 18832 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 19060 KB Output is correct
2 Correct 741 ms 19088 KB Output is correct
3 Correct 271 ms 10956 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 11220 KB Output is correct
2 Correct 905 ms 19640 KB Output is correct
3 Correct 885 ms 19608 KB Output is correct
4 Correct 929 ms 19408 KB Output is correct
5 Correct 1012 ms 19404 KB Output is correct
6 Correct 217 ms 10184 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4332 ms 35276 KB Output is correct
2 Correct 1008 ms 18792 KB Output is correct

Subtask #14
0 / 10.0

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

Subtask #15
0 / 10.0

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