Submission #1046246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046246		Zicrus	Pyramid Base (IOI08_pyramid_base)	C++17	35 / 100	5057 ms	37752 KiB

pyramid_base

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10