oj.uz

Submission #1046246

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

typedef long long ll;

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

int main() {
    ll w, h, b, n;
    cin >> w >> h >> b >> n;
    vector<rect> p(n);
    vector<ll> bL = {1}, bR = {w}, bB = {1}, bT = {h};
    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);
        bR.push_back(l-1);
        bB.push_back(t+1);
        bT.push_back(b-1);
    }
    sort(bL.begin(), bL.end());
    sort(bR.begin(), bR.end());
    sort(bB.begin(), bB.end());
    sort(bT.begin(), bT.end());

    ll res = 0;
    for (auto &l : bL) {
        for (auto &r : bR) {
            if (r - l + 1 <= res) continue;
            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) res = r-l+1;
            else break;
        }
    }
    
    for (auto &b : bB) {
        for (auto &t : bT) {
            if (t - b + 1 <= res) continue;
            vector<pair<ll, ll>> ranges = {{1, w}};
            ll numBig = ((w-1) >= (t-b));
            for (auto &rect : p) {
                if (rect.t < b || rect.b > t) continue;
                for (int i = ranges.size()-1; i >= 0; i--) {
                    bool big = (ranges[i].second-ranges[i].first) >= (t-b);
                    if (!big) continue;
                    if (rect.r >= ranges[i].second) {
                        ranges[i].second = min(ranges[i].second, rect.l-1);
                        if ((ranges[i].second-ranges[i].first) < (t-b)) numBig--;
                    }
                    else if (rect.l <= ranges[i].first) {
                        ranges[i].first = max(ranges[i].first, rect.r+1);
                        if ((ranges[i].second-ranges[i].first) < (t-b)) numBig--;
                    }
                    else if (rect.r < ranges[i].second && rect.l > ranges[i].first) {
                        numBig++;
                        ranges.push_back({ranges[i].first, min(ranges[i].second, rect.l-1)});
                        ranges[i].first = max(ranges[i].first, rect.r+1);
                        if ((ranges.back().second-ranges.back().first) < (t-b)) numBig--;
                        if ((ranges[i].second-ranges[i].first) < (t-b)) numBig--;
                    }
                }
                if (numBig <= 0) break;
            }
            if (numBig > 0) res = t-b+1;
            else break;
        }
    }

    cout << res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 2 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5017 ms 18836 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 5057 ms 33880 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 5056 ms 37752 KB Time limit exceeded
2 Halted 0 ms 0 KB -