#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 0x1fffffffffffffff;
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
#define rep(b) for(ll i = 0; i < b; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
#ifdef DEBUG
inline constexpr int __lg(int __n){ return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
#else
static_assert(0);
#endif
struct SegTree{
ll n;
vector<ll> data, lazy;
SegTree(ll n): n(n), data(n * 2), lazy(n * 2){}
ll get() const {
return data[1];
}
void add(ll l, ll r, ll val){
if(l < 0) l = 0;
if(r > n) r = n;
l += n;
r += n;
ll L = l, R = r;
for(; L < R; L /= 2, R /= 2){
if(L & 1){
data[L] += val;
lazy[L++] += val;
}
if(R & 1){
data[--R] += val;
lazy[R] += val;
}
}
r--;
while(l /= 2) data[l] = min(data[l * 2], data[l * 2 | 1]) + lazy[l];
while(r /= 2) data[r] = min(data[r * 2], data[r * 2 | 1]) + lazy[r];
}
};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
ll m, n, b, p;
cin >> m >> n >> b >> p;
using tuplis = array<ll, 4>;
vector<tuplis> in, out;
rep(p){
ll x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
x1--; y1--;
in.push_back({x1, y1, y2, c});
out.push_back({x2, y1, y2, -c});
}
sort(all(in));
sort(all(out));
auto check = [&](ll x) -> bool {
x--;
SegTree seg(n - x);
ll at1 = 0, at2 = 0;
rep(m - x){
while(at1 < p && in[at1][0] <= i + x){
seg.add(in[at1][1] - x, in[at1][2], in[at1][3]);
at1++;
}
while(at2 < p && out[at2][0] <= i){
seg.add(out[at2][1] - x, out[at2][2], out[at2][3]);
at2++;
}
if(seg.get() <= b) return true;
}
return false;
};
ll ok = 0, ng = min(n, m) + 1;
while(ng - ok > 1){
ll cen = (ok + ng) / 2;
if(check(cen)) ok = cen;
else ng = cen;
}
cout << ok << endl;
}
Compilation message
pyramid_base.cpp:13:1: error: static assertion failed
static_assert(0);
^~~~~~~~~~~~~
