oj.uz

Submission #689351

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

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

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 7 ms 732 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8532 KB Output is correct
2 Correct 308 ms 16888 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 16868 KB Output is correct
2 Correct 158 ms 8648 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 816 KB Output is correct
2 Correct 74 ms 948 KB Output is correct
3 Correct 62 ms 968 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 3680 KB Output is correct
2 Correct 405 ms 3652 KB Output is correct
3 Correct 341 ms 3644 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 10580 KB Output is correct
2 Correct 37 ms 2396 KB Output is correct
3 Correct 254 ms 18808 KB Output is correct
4 Correct 695 ms 18884 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 19060 KB Output is correct
2 Correct 1060 ms 19280 KB Output is correct
3 Correct 421 ms 10996 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 11088 KB Output is correct
2 Correct 1322 ms 19568 KB Output is correct
3 Correct 1307 ms 19588 KB Output is correct
4 Correct 1381 ms 19584 KB Output is correct
5 Correct 1485 ms 19492 KB Output is correct
6 Correct 322 ms 10188 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5050 ms 35464 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 5041 ms 40532 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 5043 ms 45616 KB Time limit exceeded
2 Halted 0 ms 0 KB -