| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1006212 | huutuan | Pyramid Base (IOI08_pyramid_base) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
struct Node{
int val, lazy;
Node (int _val=0){
val=_val, lazy=0;
}
};
struct SegmentTree{
vector<Node> t;
int n, h;
void init(int _n){
n=_n;
h=32-__builtin_clz(n);
t.assign(2*n+1, Node());
}
void apply(int k, int val){
t[k].val+=val;
if (k<n) t[k].lazy+=val;
}
void build(int k){
while (k>1) k>>=1, t[k].val=min(t[k<<1].val, t[k<<1|1].val)+t[k].lazy;
}
void push(int k){
for (int s=h; s>0; --s){
int i=k>>s;
if (t[i].lazy){
apply(i<<1, t[i].lazy);
apply(i<<1|1, t[i].lazy);
t[i].lazy=0;
}
}
}
void update(int l, int r, int val){
--l;
l+=n; r+=n;
int l0=l, r0=r;
for (; l<r; l>>=1, r>>=1){
if (l&1) apply(l++, val);
if (r&1) apply(--r, val);
}
build(l0);
build(r0-1);
}
int get(int l, int r){
--l;
l+=n; r+=n;
push(l); push(r-1);
int ans=INT_MAX;
for (; l<r; l>>=1, r>>=1){
if (l&1) ans=min(ans, t[l++].val);
if (r&1) ans=min(ans, t[--r].val);
}
return ans;
}
} st;
struct Rect{
int x1, y1, x2, y2, z;
Rect(){ x1=0, y1=0, x2=0, y2=0, z=0; }
};
const int N=5e5+10;
int m, n, p, q;
Rect a[N], b[N];
pair<pair<int, int>, pair<int, int>> events[N*2];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> p >> q >> m >> n;
st.init(q);
int l=1, r=min(p, q);
for (int i=1; i<=n; ++i){
cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2 >> a[i].z;
if (m==0){
r=min(r, max({a[i].x1-1, a[i].y1-1, p-a[i].x2, q-a[i].y2}));
}
}
l=max(l, r-1e5);
while (l<=r){
int mid=(l+r)>>1;
int sz=0;
for (int i=1; i<=n; ++i){
events[sz++]={{max(1, a[i].x1-mid+1), a[i].z}, {max(1, a[i].y1-mid+1), a[i].y2}};
events[sz++]={{a[i].x2+1, -a[i].z}, {max(1, a[i].y1-mid+1), a[i].y2}};
}
sort(events, events+sz);
bool check=0;
for (int i=0; i<sz; ++i){
st.update(events[i].second.first, events[i].second.second, events[i].first.second);
if (i==sz-1 || events[i].first.first!=events[i+1].first.first){
if (events[i].first.first+mid-1<=p){
check|=st.get(1, q-mid+1)<=m;
}
}
}
if (check) l=mid+1;
else r=mid-1;
}
cout << r << '\n';
return 0;
}