oj.uz

Submission #1046267

# Submission time Handle Problem Language Result Execution time Memory
1046267 2024-08-06T12:18:48 Z Zicrus Pyramid Base (IOI08_pyramid_base) C++17
35 / 100
 5000 ms 18372 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct rect {
    ll l, r, b, t;
};

ll w, h, b, n;
vector<rect> p;
vector<ll> bL;

bool poss(ll goal) {
    for (auto &l : bL) {
        ll r = l + goal - 1;
        if (r > w) break;
        vector<pair<ll, ll>> ranges = {{1, h}};
        ll numBig = ((h-1) >= (r-l));
        for (auto &rect : p) {
            if (rect.r < l || rect.l > r) continue;
            for (int i = ranges.size()-1; i >= 0; i--) {
                bool big = (ranges[i].second-ranges[i].first) >= (r-l);
                if (!big) continue;
                if (rect.t >= ranges[i].second) {
                    ranges[i].second = min(ranges[i].second, rect.b-1);
                    if ((ranges[i].second-ranges[i].first) < (r-l)) numBig--;
                }
                else if (rect.b <= ranges[i].first) {
                    ranges[i].first = max(ranges[i].first, rect.t+1);
                    if ((ranges[i].second-ranges[i].first) < (r-l)) numBig--;
                }
                else if (rect.t < ranges[i].second && rect.b > ranges[i].first) {
                    numBig++;
                    ranges.push_back({ranges[i].first, min(ranges[i].second, rect.b-1)});
                    ranges[i].first = max(ranges[i].first, rect.t+1);
                    if ((ranges.back().second-ranges.back().first) < (r-l)) numBig--;
                    if ((ranges[i].second-ranges[i].first) < (r-l)) numBig--;
                }
            }
            if (numBig <= 0) break;
        }
        if (numBig > 0) return true;
    }
    return false;
}

int main() {
    cin >> w >> h >> b >> n;
    p = vector<rect>(n);
    bL = {1};
    for (auto &e : p) {
        ll l, b, r, t, c;
        cin >> l >> b >> r >> t >> c;
        e = {l, r, b, t};
        bL.push_back(r+1);
    }
    sort(bL.begin(), bL.end());

    ll left = 0, right = min(w, h);
    while (left < right) {
        ll mid = (left+right+1) / 2;
        if (poss(mid)) {
            left = mid;
        }
        else {
            right = mid-1;
        }
    }

    cout << left;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 13 ms 476 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 344 KB Output is correct
2 Correct 1 ms 472 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 238 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2881 ms 1148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5027 ms 8644 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 5067 ms 14708 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 5051 ms 18372 KB Time limit exceeded
2 Halted 0 ms 0 KB -