oj.uz

Submission #220644

# Submission time Handle Problem Language Result Execution time Memory
220644 2020-04-08T10:43:51 Z dolphingarlic Pyramid Base (IOI08_pyramid_base) C++14
20 / 100
 1425 ms 101800 KB 
#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;
        if (H < W) {
            swap(H, W);
            FOR(i, 0, N) swap(obsts[i].x1, obsts[i].y1), swap(obsts[i].x2, obsts[i].y2);
        }

        sort(obsts.begin(), obsts.end(), compare_y());
        set<obst, compare_x> edges{obst{0, 0, 0, 0}, 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Runtime error 6 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 3664 KB Output is correct
2 Runtime error 262 ms 29048 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 5240 KB Output is correct
2 Runtime error 833 ms 76408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 6924 KB Output is correct
2 Runtime error 1425 ms 101800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -