oj.uz

Submission #891682

# Submission time Handle Problem Language Result Execution time Memory
891682 2023-12-23T15:36:52 Z Macker Pyramid Base (IOI08_pyramid_base) C++17
30 / 100
 5000 ms 108940 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define cmpr(x) lower_bound(all(crds), x) - crds.begin()
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
 
class SegTree{
public:
    vector<int> st;
    vector<int> lz;
    int len = 1;
    SegTree(int n){
        while(len < n) len *= 2;
        st.resize(2 * len, INT_MAX);
        for (int i = len; i < len + n; i++){
            st[i] = 0;
        }
        for (int i = len - 1; i > 0; i--) {
            st[i] = min(st[i * 2], st[i * 2 + 1]);
        }
        
        lz.resize(2 * len, 0);
    }
    void prop(int i){
        st[i * 2] += lz[i];
        st[i * 2 + 1] += lz[i];
        lz[i * 2] += lz[i];
        lz[i * 2 + 1] += lz[i];
        lz[i] = 0;
    }
 
    void add(int f, int t, int v, int i, int s, int e){
        if(f >= e || s >= t) return;
        if(f <= s && e <= t){
            st[i] += v;
            lz[i] += v;
            return;
        }
        prop(i);
        add(f, t, v, i * 2, s, (s + e) / 2);
        add(f, t, v, i * 2 + 1, (s + e) / 2, e);
        st[i] = min(st[i * 2], st[i * 2 + 1]);
    }
    void add(int f, int t, int v) {
        add(f, t, v, 1, 0, len);
    }
};


bool can(int d, vector<array<int, 5>> v, int w, int h){
    w -= d;
    h -= d;
    vector<int> crds;
    for (auto &i : v) {
        i[0] -= d;
        i[1] -= d;
 
        for (int j = 0; j < 4; j++) {
            i[0] = max(0, i[0]);
            i[1] = max(0, i[1]);
            i[2] = min(w - 1, i[2]);
            i[3] = min(h - 1, i[3]);
        }
        crds.push_back(i[0]);
        crds.push_back(i[2]);
    }
    sort(all(crds));
    crds.erase(unique(all(crds)), crds.end());
 
    vector<vector<array<int, 3>>> ev(h + 1); //[y][i] -> t(0s, 1e), x, xx
    SegTree st(crds.size() * 2 - 1);
    for (auto &i : v) {
        ev[i[1]].push_back({0, i[0], i[2]});
        ev[i[3] + 1].push_back({1, i[0], i[2]});
    }
    int y = 0;
    for (auto &es : ev) {
        for (auto &e : es) {
            auto& [t, x, xx] = e;
            int cx = cmpr(x);
            int cxx = cmpr(xx);
            if(t == 0){
                st.add(cx * 2, cxx * 2 + 1, 1);
            }
            else{
                st.add(cx * 2, cxx * 2 + 1, -1);
            }
        }
        
        if(st.st[1] == 0 && y != h) return true;
        y++;
    }
    
    return false;
}
 
int main()
{
    int w, h; cin >> w >> h;
    int b; cin >> b;
    if(b != 0) return 1;
    int n; cin >> n;
    vector<array<int, 5>> v(n);
    for (auto &i : v){
        cin >> i[0] >> i[1] >> i[2] >> i[3] >> i[4];
        for (int j = 0; j < 4; j++)
            i[j]--;
    }
 
 
    int l = -1, r = min(w, h), mid;
    while(l < r){
        mid = (l + r + 1) / 2;
        if(can(mid, v, w, h)) l = mid;
        else r = mid - 1;
    }
    
    cout << l + 1 << endl;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 764 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12120 KB Output is correct
2 Correct 142 ms 24144 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 22452 KB Output is correct
2 Correct 32 ms 12124 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 344 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 344 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 68708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5049 ms 75328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5034 ms 108940 KB Time limit exceeded
2 Halted 0 ms 0 KB -