oj.uz

Submission #891916

# Submission time Handle Problem Language Result Execution time Memory
891916 2023-12-24T12:21:15 Z Macker Pyramid Base (IOI08_pyramid_base) C++17
80 / 100
 5000 ms 148964 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

int st[2097157];
int lz[2097157];
int len = 1;

void init(int n){
    len = 1;
    while(len < n) len *= 2;
    for (int i = len; i < len + n; i++) {
        st[i] = 0;
        lz[i] = 0;
    }
    for (int i = len + n; i < 2 * len; i++){
        st[i] = INT_MAX;
        lz[i] = 0;
    }
    for (int i = len - 1; i > 0; i--) {
        st[i] = min(st[i * 2], st[i * 2 + 1]);
        lz[i] = 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 = 1, int s = 0, int e = len){
    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]);
}

vector<tuple<int, int, int, int>> ev[1000005]; //[y][i] -> t(0s, 1e), x, xx, c
bool can(int d, vector<array<int, 5>> v, int w, int h, int b){
    w -= d;
    h -= d;
    for (auto &i : v) {
        i[0] = max(0, i[0] - d);
        i[1] = max(0, i[1] - d);
        i[2] = min(w - 1, i[2]);
        i[3] = min(h - 1, i[3]);
    }

    init(w);
    for (int i = 0; i < 1000005; i++) {
        ev[i] = {};
    }
    for (auto& i : v) {
        ev[i[1]].push_back({0, i[0], i[2], i[4]});
        ev[i[3] + 1].push_back({1, i[0], i[2], i[4]});
    }
    int y = 0;
    for (auto& es : ev) {
        for (auto& e : es) {
            auto& [t, x, xx, c] = e;
            if(t == 0){
                add(x, xx + 1, c);
            }
            else{
                add(x, xx + 1, -c);
            }
        }
        
        if(y >= h) break;
        if(st[1] <= b) return true;
        y++;
    }
    
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int w, h; cin >> w >> h;
    int b; cin >> b;
    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, b)) l = mid;
        else r = mid - 1;
    }
    
    cout << l + 1 << "\n";
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 35824 KB Output is correct
2 Correct 158 ms 40748 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 41032 KB Output is correct
2 Correct 97 ms 35716 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28920 KB Output is correct
2 Correct 75 ms 28232 KB Output is correct
3 Correct 80 ms 28284 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 32076 KB Output is correct
2 Correct 274 ms 31944 KB Output is correct
3 Correct 226 ms 32504 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 45312 KB Output is correct
2 Correct 138 ms 44996 KB Output is correct
3 Correct 58 ms 32972 KB Output is correct
4 Correct 652 ms 51624 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 53140 KB Output is correct
2 Correct 958 ms 53564 KB Output is correct
3 Correct 259 ms 46664 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 49884 KB Output is correct
2 Correct 1012 ms 56788 KB Output is correct
3 Correct 909 ms 56788 KB Output is correct
4 Correct 943 ms 56828 KB Output is correct
5 Correct 880 ms 56716 KB Output is correct
6 Correct 219 ms 48680 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4088 ms 99820 KB Output is correct
2 Correct 1656 ms 148964 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5100 ms 118384 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 5072 ms 132324 KB Time limit exceeded
2 Halted 0 ms 0 KB -