oj.uz

Submission #689354

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

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("strict-overflow")

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';
}

Compilation message

pyramid_base.cpp:6:39: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
    6 | #pragma GCC optimize("strict-overflow")
      |                                       ^
pyramid_base.cpp:16:40: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
   16 |     SegmentTreeMin(size_t n, T _neutral)
      |                                        ^
pyramid_base.cpp:29:48: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
   29 |     void propagate(size_t k, size_t x, size_t y)
      |                                                ^
pyramid_base.cpp:38:75: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
   38 |     void increment_r(size_t i, size_t j, T v, size_t k, size_t x, size_t y)
      |                                                                           ^
pyramid_base.cpp:57:43: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
   57 |     void increment(size_t i, size_t j, T v)
      |                                           ^
pyramid_base.cpp:62:24: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
   62 |     T get_global_min() const
      |                        ^~~~~
pyramid_base.cpp:77:46: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
   77 |     Event(int _x, int _y1, int _y2, int _cost)
      |                                              ^
pyramid_base.cpp:85:36: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
   85 |     bool operator<(Event const &e) const
      |                                    ^~~~~
pyramid_base.cpp:92:78: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
   92 |     vector<Rectangle> const &rectangles, int m, int n, int side_length, int b)
      |                                                                              ^
pyramid_base.cpp:124:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
  124 | int main()
      |          ^

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8532 KB Output is correct
2 Correct 345 ms 16924 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 16864 KB Output is correct
2 Correct 144 ms 8708 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 852 KB Output is correct
2 Correct 74 ms 968 KB Output is correct
3 Correct 61 ms 960 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 3652 KB Output is correct
2 Correct 412 ms 3776 KB Output is correct
3 Correct 354 ms 3756 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 10800 KB Output is correct
2 Correct 38 ms 2368 KB Output is correct
3 Correct 263 ms 18812 KB Output is correct
4 Correct 757 ms 18880 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 19036 KB Output is correct
2 Correct 1131 ms 19056 KB Output is correct
3 Correct 432 ms 10952 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 11212 KB Output is correct
2 Correct 1365 ms 19340 KB Output is correct
3 Correct 1280 ms 19496 KB Output is correct
4 Correct 1372 ms 19468 KB Output is correct
5 Correct 1353 ms 19524 KB Output is correct
6 Correct 328 ms 10192 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5080 ms 35336 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 5082 ms 40264 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 5053 ms 45368 KB Time limit exceeded
2 Halted 0 ms 0 KB -