oj.uz

Submission #1046278

# Submission time Handle Problem Language Result Execution time Memory
1046278 2024-08-06T12:23:00 Z Zicrus Pyramid Base (IOI08_pyramid_base) C++17
5 / 100
 1722 ms 17088 KB 
#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.0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 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 10 ms 1164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

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

Subtask #15
0 / 10.0

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