#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
#define ui unsigned int
const int N=1e6+10;
struct segment_tree
{
int t[N*2],d[N*2],n;
void apply(int p, int value) {
t[p] += value;
d[p] += value;
}
void build(int p) {
while (p > 1) p >>= 1, t[p] = min(t[p<<1], t[p<<1|1]) + d[p];
}
void upd(int l, int r, int value) {
l += n - 1, r += n;
int l0 = l, r0 = r;
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) apply(l++, value);
if (r&1) apply(--r, value);
}
build(l0);
build(r0 - 1);
}
int get() { return t[1];}
void init(int x)
{
n=x;
memset(t,0,sizeof(t));
memset(d,0,sizeof(d));
}
} seg;
struct obs{int x1,x2,y1,y2,c;};
obs a[N];
int n,m,B,p;
struct event{int l,r,x;};
vector<event> vt[N];
bool check(int l)
{
for (int i=1;i<=m;i++) vt[i].clear();
for (int i=1;i<=p;i++)
{
int x1=max(a[i].x1-l+1,1);
int y1=max(a[i].y1-l+1,1);
int x2=min(a[i].x2,m-l+1);
int y2=min(a[i].y2,n-l+1);
if (x1>x2 || y1>y2) continue;
int c=a[i].c;
vt[x1].pb({y1,y2,c});
vt[x2+1].pb({y1,y2,-c});
}
seg.init(n-l+1);
for (int i=1;i<=m-l+1;i++)
{
for (event e : vt[i]) seg.upd(e.l,e.r,e.x);
if (seg.get()<=B) return true;
}
return false;
}
int main()
{
//freopen("ss.inp","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>m>>n>>B>>p;
for (int i=1;i<=p;i++) cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2>>a[i].c,a[i].c=min(a[i].c,B+1);
int l=1,r=min(m,n),ans=0;
while (l<=r)
{
int mid=(l+r)/2;
if (check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
39372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
39476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
39492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
50 ms |
39576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
39840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
117 ms |
39952 KB |
Output is correct |
2 |
Correct |
171 ms |
39980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
173 ms |
40096 KB |
Output is correct |
2 |
Correct |
129 ms |
39840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
40600 KB |
Output is correct |
2 |
Correct |
80 ms |
40056 KB |
Output is correct |
3 |
Correct |
73 ms |
40184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
177 ms |
43076 KB |
Output is correct |
2 |
Correct |
267 ms |
42852 KB |
Output is correct |
3 |
Correct |
226 ms |
43220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
314 ms |
47320 KB |
Output is correct |
2 |
Correct |
115 ms |
44356 KB |
Output is correct |
3 |
Correct |
131 ms |
42184 KB |
Output is correct |
4 |
Correct |
502 ms |
49424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
549 ms |
49912 KB |
Output is correct |
2 |
Correct |
831 ms |
51552 KB |
Output is correct |
3 |
Correct |
255 ms |
47276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
436 ms |
50160 KB |
Output is correct |
2 |
Correct |
1069 ms |
53792 KB |
Output is correct |
3 |
Correct |
1010 ms |
53372 KB |
Output is correct |
4 |
Correct |
1087 ms |
53724 KB |
Output is correct |
5 |
Correct |
1100 ms |
53784 KB |
Output is correct |
6 |
Correct |
234 ms |
48224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4861 ms |
80312 KB |
Output is correct |
2 |
Correct |
1430 ms |
79748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5069 ms |
87244 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5037 ms |
92648 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |