#include <bits/stdc++.h>
using namespace std;
const int MP = 4e5+5;
int M,N,B,P;
struct Obs{
int sx,ex,sy,ey,val;
Obs(){};
Obs(int a, int b, int c, int d, int e){
sx = a, sy = b, ex = c, ey = d, val = e;
}
} O[MP];
struct Event{
int x,sy,ey,c;
Event(){};
Event(int a, int y1, int y2, int v){
x = a, sy = y1, ey = y2, c = v;
}
bool operator < (const Event &A) const{
return x<A.x;
}
} E[2*MP];
int ST[4*MP],SL[4*MP];
void upt(int l, int r, int c, int s, int e, int pos)
{
if(e<l || s>r) return;
if(l<=s && e<=r){
ST[pos] += c;
if(s==e) SL[pos] = ST[pos] ? 1 : 0;
else SL[pos] = ST[pos] ? e-s+1 : SL[2*pos] + SL[2*pos+1];
return;
}
int m = (s+e)/2;
upt(l,r,c,s,m,2*pos);
upt(l,r,c,m+1,e,2*pos+1);
SL[pos] = ST[pos]? e-s+1 : SL[2*pos] + SL[2*pos+1];
}
bool isable(int L)
{
int sx,ex,sy,ey;
vector<int> X,Y;
for(int i=0; i<P; i++){
sx = max(O[i].sx,L);
ex = min(O[i].ex+L,M+1);
sy = max(O[i].sy-L+1,1);
ey = min(O[i].ey,N-L+1);
X.push_back(sx);
X.push_back(ex);
Y.push_back(sy);
Y.push_back(ey);
E[i] = Event(sx,sy,ey,1);
E[i+P] = Event(ex,sy,ey,-1);
}
X.push_back(L);
X.push_back(M+1);
Y.push_back(1);
Y.push_back(N-L+1);
sort(X.begin(),X.end());
sort(Y.begin(),Y.end());
X.erase(unique(X.begin(),X.end()),X.end());
Y.erase(unique(Y.begin(),Y.end()),Y.end());
for(int i=0; i<2*P; i++){
E[i].x = lower_bound(X.begin(),X.end(),E[i].x)-X.begin();
E[i].sy = lower_bound(Y.begin(),Y.end(),E[i].sy)-Y.begin();
E[i].ey = lower_bound(Y.begin(),Y.end(),E[i].ey)-Y.begin();
}
sort(E,E+2*P);
int tmp = 0;
for(int i=0; i<2*P; i++){
if(tmp!=E[i].x){
if(SL[1]!=Y.size()) return true;
tmp = E[i].x;
}
upt(E[i].sy,E[i].ey,E[i].c,0,Y.size()-1,1);
}
return false;
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
//freopen("input.txt","r",stdin);
cin >> M >> N >> B >> P;
if(B!=0) return 0;
int sx,ex,sy,ey,val;
for(int i=0; i<P; i++){
cin >> sx >> sy >> ex >> ey >> val;
O[i] = Obs(sx,sy,ex,ey,val);
}
int s = 0, e = min(M,N), m;
while(s<e){
m = (s+e+1)/2;
if(isable(m)) s = m;
else e = m-1;
}
cout << s;
}
Compilation message
pyramid_base.cpp: In function 'bool isable(int)':
pyramid_base.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(SL[1]!=Y.size()) return true;
~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
504 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
504 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5082 ms |
26560 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5087 ms |
36740 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5007 ms |
44152 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |