#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e6;
const int MAXP = 4e5;
const ll INF = 1e18;
struct Rect
{
int x1, y1, x2, y2, w;
};
struct Line
{
int x, y1, y2, w;
bool operator < (const Line &p) const { return x<p.x; }
};
int N, M, P;
ll B;
Rect A[MAXP+10];
struct SEG
{
ll tree[MAXN*4+10], lazy[MAXN*4+10];
void init()
{
memset(tree, 0, sizeof(tree));
memset(lazy, 0, sizeof(lazy));
}
void busy(int node, int tl, int tr)
{
if(lazy[node]==0) return;
tree[node]+=lazy[node];
if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
lazy[node]=0;
}
void update(int node, int tl, int tr, int l, int r, ll v)
{
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
lazy[node]+=v;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, v);
update(node*2+1, mid+1, tr, l, r, v);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
}seg;
struct Node
{
int val, cnt, lcnt, rcnt, len;
Node() : val(0), cnt(0), lcnt(0), rcnt(0), len(0) {}
};
Node operator + (const Node &p, const Node &q)
{
Node ret;
ret.len=p.len+q.len;
ret.val=min(p.val, q.val);
if(p.val<q.val)
{
ret.cnt=p.cnt;
ret.lcnt=p.lcnt;
ret.rcnt=0;
}
else if(p.val>q.val)
{
ret.cnt=q.cnt;
ret.rcnt=q.rcnt;
ret.lcnt=0;
}
else
{
ret.cnt=max({p.cnt, q.cnt, p.rcnt+q.lcnt});
ret.lcnt=max(p.lcnt, (p.len==p.cnt)*(p.len+q.lcnt));
ret.rcnt=max(q.rcnt, (q.len==q.cnt)*(q.len+p.rcnt));
}
return ret;
}
struct SEG2
{
Node tree[MAXN*4+10];
int lazy[MAXN*4+10];
void init(int node, int tl, int tr)
{
lazy[node]=0;
if(tl==tr)
{
tree[node].len=1;
tree[node].val=0;
tree[node].cnt=tree[node].lcnt=tree[node].rcnt=1;
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=tree[node*2]+tree[node*2+1];
}
void busy(int node, int tl, int tr)
{
if(lazy[node]==0) return;
if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
tree[node].val+=lazy[node];
lazy[node]=0;
}
void update(int node, int tl, int tr, int l, int r, int v)
{
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
lazy[node]+=v;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, v);
update(node*2+1, mid+1, tr, l, r, v);
tree[node]=tree[node*2]+tree[node*2+1];
}
int query(int NN)
{
busy(1, 1, NN);
if(tree[1].val!=0) return 0;
else return tree[1].cnt;
}
}seg2;
bool solve(int d)
{
int i, j;
vector<Line> V;
ll val=INF;
for(i=1; i<=P; i++)
{
V.push_back({A[i].x1, A[i].y1, A[i].y2+d-1, A[i].w});
V.push_back({A[i].x2+d, A[i].y1, A[i].y2+d-1, -A[i].w});
}
sort(V.begin(), V.end());
seg.init();
for(i=0; i<V.size();)
{
int x=V[i].x;
seg.busy(1, d, N);
if(d<=x-1) val=min(val, seg.tree[1]);
if(x>M) break;
for(; i<V.size() && V[i].x==x; i++)
{
seg.update(1, d, N, V[i].y1, V[i].y2, V[i].w);
}
}
seg.busy(1, d, N);
val=min(val, seg.tree[1]);
if(val<=B) return true;
return false;
}
int main()
{
int i, j;
scanf("%d%d%lld%d", &M, &N, &B, &P);
for(i=1; i<=P; i++) scanf("%d%d%d%d%d", &A[i].x1, &A[i].y1, &A[i].x2, &A[i].y2, &A[i].w);
if(B!=0)
{
int lo=0, hi=min(N, M)+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(solve(mid)) lo=mid;
else hi=mid;
}
printf("%d\n", lo);
}
else
{
int l, r;
vector<Line> V1, V2;
int ans=0;
V1.clear(); V2.clear();
for(i=1; i<=P; i++)
{
V1.push_back({A[i].x1, A[i].y1, A[i].y2});
V2.push_back({A[i].x2+1, A[i].y1, A[i].y2});
}
sort(V1.begin(), V1.end());
sort(V2.begin(), V2.end());
seg2.init(1, 1, N);
for(l=1, r=1, i=0, j=0; r<=M; r++)
{
for(; i<V1.size() && V1[i].x==r; i++) seg2.update(1, 1, N, V1[i].y1, V1[i].y2, 1);
for(; l<r; l++)
{
for(; j<V2.size() && V2[j].x==l; j++) seg2.update(1, 1, N, V2[j].y1, V2[j].y2, -1);
if(!(seg2.query(N)<=r-l+1)) break;
ans=max(ans, seg2.query(N));
}
}
V1.clear(); V2.clear();
for(i=1; i<=P; i++)
{
V1.push_back({A[i].y1, A[i].x1, A[i].x2});
V2.push_back({A[i].y2+1, A[i].x1, A[i].x2});
}
sort(V1.begin(), V1.end());
sort(V2.begin(), V2.end());
seg2.init(1, 1, M);
for(l=1, r=1, i=0, j=0; r<=N; r++)
{
for(; i<V1.size() && V1[i].x==r; i++) seg2.update(1, 1, M, V1[i].y1, V1[i].y2, 1);
for(; l<r; l++)
{
for(; j<V2.size() && V2[j].x==l; j++) seg2.update(1, 1, M, V2[j].y1, V2[j].y2, -1);
if(!(seg2.query(M)<=r-l+1)) break;
ans=max(ans, seg2.query(M));
}
}
printf("%d\n", ans);
}
}
Compilation message
pyramid_base.cpp: In member function 'void SEG::update(int, int, int, int, int, ll)':
pyramid_base.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
pyramid_base.cpp: In member function 'void SEG2::init(int, int, int)':
pyramid_base.cpp:106:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
pyramid_base.cpp: In member function 'void SEG2::update(int, int, int, int, int, int)':
pyramid_base.cpp:130:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
pyramid_base.cpp: In function 'bool solve(int)':
pyramid_base.cpp:157:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<V.size();)
~^~~~~~~~~
pyramid_base.cpp:163:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i<V.size() && V[i].x==x; i++)
~^~~~~~~~~
pyramid_base.cpp:146:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:186:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
pyramid_base.cpp:210:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i<V1.size() && V1[i].x==r; i++) seg2.update(1, 1, N, V1[i].y1, V1[i].y2, 1);
~^~~~~~~~~~
pyramid_base.cpp:213:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; j<V2.size() && V2[j].x==l; j++) seg2.update(1, 1, N, V2[j].y1, V2[j].y2, -1);
~^~~~~~~~~~
pyramid_base.cpp:231:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i<V1.size() && V1[i].x==r; i++) seg2.update(1, 1, M, V1[i].y1, V1[i].y2, 1);
~^~~~~~~~~~
pyramid_base.cpp:234:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; j<V2.size() && V2[j].x==l; j++) seg2.update(1, 1, M, V2[j].y1, V2[j].y2, -1);
~^~~~~~~~~~
pyramid_base.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld%d", &M, &N, &B, &P);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:179:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=P; i++) scanf("%d%d%d%d%d", &A[i].x1, &A[i].y1, &A[i].x2, &A[i].y2, &A[i].w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
78584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
78712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
78712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
78840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
79736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
86944 KB |
Output is correct |
| 2 |
Correct |
112 ms |
87032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
86956 KB |
Output is correct |
| 2 |
Correct |
128 ms |
86964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
141924 KB |
Output is correct |
| 2 |
Correct |
224 ms |
141908 KB |
Output is correct |
| 3 |
Correct |
214 ms |
141876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
446 ms |
143076 KB |
Output is correct |
| 2 |
Correct |
497 ms |
142972 KB |
Output is correct |
| 3 |
Correct |
426 ms |
143180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
518 ms |
143968 KB |
Output is correct |
| 2 |
Correct |
162 ms |
143752 KB |
Output is correct |
| 3 |
Correct |
294 ms |
143756 KB |
Output is correct |
| 4 |
Correct |
906 ms |
144024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
756 ms |
144332 KB |
Output is correct |
| 2 |
Correct |
967 ms |
144420 KB |
Output is correct |
| 3 |
Correct |
394 ms |
144552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
557 ms |
144700 KB |
Output is correct |
| 2 |
Correct |
1330 ms |
144776 KB |
Output is correct |
| 3 |
Correct |
1289 ms |
144692 KB |
Output is correct |
| 4 |
Correct |
1248 ms |
144844 KB |
Output is correct |
| 5 |
Correct |
1265 ms |
144764 KB |
Output is correct |
| 6 |
Correct |
389 ms |
144892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1112 ms |
102988 KB |
Output is correct |
| 2 |
Correct |
601 ms |
102468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1455 ms |
111024 KB |
Output is correct |
| 2 |
Correct |
1486 ms |
110636 KB |
Output is correct |
| 3 |
Correct |
887 ms |
110244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1846 ms |
119084 KB |
Output is correct |
| 2 |
Correct |
2248 ms |
118564 KB |
Output is correct |
| 3 |
Correct |
2255 ms |
118352 KB |
Output is correct |
| 4 |
Correct |
1931 ms |
118316 KB |
Output is correct |
| 5 |
Correct |
1279 ms |
118572 KB |
Output is correct |
