Submission #220639

#	Time	Username	Problem	Language	Result	Execution time	Memory
220639		dolphingarlic	Pyramid Base (IOI08_pyramid_base)	C++14	20 / 100	1406 ms	112772 KiB

pyramid_base

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

namespace no_remove {
    struct obst {
        int x1, y1, x2, y2;
    };

    struct compare_x {
        bool operator()(const obst &a, const obst &b) const {
            return tie(a.x1, a.y1) < tie(b.x1, b.y1);
        }
    };

    struct compare_y {
        bool operator()(const obst &a, const obst &b) const { return a.y1 < b.y1; }
    };

    void solve(int H, int W) {
        int N, C;
        cin >> N;
        vector<obst> obsts(N);
        FOR(i, 0, N) cin >> obsts[i].x1 >> obsts[i].y1 >> obsts[i].x2 >> obsts[i].y2 >> C;

        sort(obsts.begin(), obsts.end(), compare_y());
        set<obst, compare_x> edges{obst{0, -1, 0, -1}, obst{H + 1, W + 1, H + 1, W + 1}};
        multiset<int> gaps{H};
        int ans = 0;
        int p = 0;
        FOR(i, -1, N) {
            int y0 = -1;
            if (~i) {
                const obst &o = obsts[i];
                y0 = o.y2;
                auto pos = edges.find(o);
                assert(pos != edges.end());
                auto a = prev(pos);
                auto b = next(pos);
                gaps.erase(gaps.find(o.x1 - a->x2 - 1));
                gaps.erase(gaps.find(b->x1 - o.x2 - 1));
                gaps.insert(b->x1 - a->x2 - 1);
                edges.erase(pos);
            }
            if (p < i) p = i;
            int y1 = (p == N) ? W : obsts[p].y1;
            ans = max(ans, min(y1 - y0 - 1, *gaps.rbegin()));
            while (p < N && obsts[p].y1 - y0 - 1 <= *gaps.rbegin()) {
                const obst &o = obsts[p];
                auto b = edges.lower_bound(o);
                auto a = prev(b);
                gaps.erase(gaps.find(b->x1 - a->x2 - 1));
                gaps.insert(o.x1 - a->x2 - 1);
                gaps.insert(b->x1 - o.x2 - 1);
                edges.insert(b, o);
                p++;
                y1 = (p == N) ? W : obsts[p].y1;
                ans = max(ans, min(y1 - y0 - 1, *gaps.rbegin()));
            }
        }
        cout << ans << '\n';
    }
}

namespace yes_remove {
    void solve(int H, int W, int B) {

    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int H, W, B;
    cin >> H >> W >> B;
    if (B) yes_remove::solve(H, W, B);
    else no_remove::solve(H, W);
    return 0;
}

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