oj.uz

Submission #689344

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

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 (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 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8532 KB Output is correct
2 Correct 215 ms 16876 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 16920 KB Output is correct
2 Correct 80 ms 8776 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 964 KB Output is correct
2 Correct 60 ms 1072 KB Output is correct
3 Correct 46 ms 1068 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 4100 KB Output is correct
2 Correct 289 ms 4188 KB Output is correct
3 Correct 255 ms 4276 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 11316 KB Output is correct
2 Correct 30 ms 2812 KB Output is correct
3 Correct 245 ms 19252 KB Output is correct
4 Correct 541 ms 19460 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 19776 KB Output is correct
2 Correct 867 ms 20088 KB Output is correct
3 Correct 341 ms 11668 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 12192 KB Output is correct
2 Correct 1207 ms 20328 KB Output is correct
3 Correct 1147 ms 20228 KB Output is correct
4 Correct 1152 ms 20308 KB Output is correct
5 Correct 1257 ms 20180 KB Output is correct
6 Correct 330 ms 11080 KB Output is correct

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5059 ms 48912 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 5094 ms 56976 KB Time limit exceeded
2 Halted 0 ms 0 KB -