This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
/*bool operator < (const Obs &A) const{
return
}*/
} 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],L[4*MP];
void upt(int l, int r, int c, int s, int e, int pos)
{
if(e<l || s>r) return;
/*if(L[pos] && s!=e){
ST[2*pos] += L[pos];
ST[2*pos+1] += L[pos];
L[2*pos] += L[pos];
L[2*pos+1] += L[pos];
L[pos] = 0;
}*/
if(l<=s && e<=r){
ST[pos] += c;
//L[pos] += c;
return;
}
int m = (s+e)/2;
upt(l,r,c,s,m,2*pos);
upt(l,r,c,m+1,e,2*pos+1);
}
int sum(int l, int r, int s, int e, int pos)
{
if(e<l || s>r) return 0;
/*if(L[pos] && s!=e){
ST[2*pos] += L[pos];
ST[2*pos+1] += L[pos];
L[2*pos] += L[pos];
L[2*pos+1] += L[pos];
L[pos] = 0;
}*/
if(l<=s && e<=r){
if(ST[pos]) return e-s+1;
}
if(s==e) return 0;
int m = (s+e)/2;
return sum(l,r,s,m,2*pos) + sum(l,r,m+1,e,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+1,M+1);
sy = max(O[i].sy-L,1);
ey = min(O[i].ey,N-L+1);
//cout << sx << ex << sy << ey << '\n';
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 len,tmp = 0, S = 0;
for(int i=0; i<2*P; i++){
if(tmp!=E[i].x){
len = sum(E[i].sy,E[i].ey,0,Y.size(),1);
cout << L << ' ' << len << '\n';
S += len*(E[i].x-tmp);
tmp = E[i].x;
}
upt(E[i].sy,E[i].ey,E[i].c,0,Y.size(),1);
}
//cout << S;
//cout << X.size()-1) << Y.size();
if(S==(X.size()-1)*Y.size()) return false;
return true;
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
//freopen("input.txt","r",stdin);
cin >> M >> N >> B >> P;
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 = 1, e = min(M,N), m;
//isable(5);
while(s<e){
m = (s+e+1)/2;
if(isable(m)) s = m;
else e = m-1;
}
cout << s;
}
Compilation message (stderr)
pyramid_base.cpp: In function 'bool isable(int)':
pyramid_base.cpp:111:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(S==(X.size()-1)*Y.size()) return false;
~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |