oj.uz

Submission #689355

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

#pragma GCC optimize("O3")
#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 2 ms 340 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8532 KB Output is correct
2 Correct 166 ms 16920 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 16860 KB Output is correct
2 Correct 75 ms 8636 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 880 KB Output is correct
2 Correct 48 ms 1012 KB Output is correct
3 Correct 40 ms 944 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 3772 KB Output is correct
2 Correct 260 ms 3652 KB Output is correct
3 Correct 200 ms 3652 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 10600 KB Output is correct
2 Correct 37 ms 2416 KB Output is correct
3 Correct 179 ms 18816 KB Output is correct
4 Correct 479 ms 18772 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 19028 KB Output is correct
2 Correct 723 ms 19236 KB Output is correct
3 Correct 296 ms 10872 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 11208 KB Output is correct
2 Correct 933 ms 19448 KB Output is correct
3 Correct 897 ms 19456 KB Output is correct
4 Correct 1000 ms 19372 KB Output is correct
5 Correct 1010 ms 19376 KB Output is correct
6 Correct 245 ms 10192 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4379 ms 35312 KB Output is correct
2 Correct 1058 ms 24136 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5057 ms 40364 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 5040 ms 45468 KB Time limit exceeded
2 Halted 0 ms 0 KB -