Submission #1046278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046278		Zicrus	Pyramid Base (IOI08_pyramid_base)	C++17	5 / 100	1722 ms	17088 KiB

pyramid_base

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2,bmi,bmi2")

#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);
    }
    mt19937 mt(time(0));
    shuffle(p.begin(), p.end(), mt);
    shuffle(bL.begin(), bL.end(), mt);

    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 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 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