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 <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;
typedef long long ll;
int N, M, P;
struct SEG{
SEG (int l, int r, ll lazy, ll mn) : l(l), r(r), lazy(lazy), mn(mn) {}
int l, r;
ll lazy, mn;
};
vector<SEG> seg;
SEG ss(-1, -1, 0, 0);
struct SQ{
SQ (int x1, int x2, int y1, int y2, ll c) : x1(x1), x2(x2), y1(y1), y2(y2), c(c) {}
int x1, x2, y1, y2;
ll c;
};
vector<SQ> sc;
ll B;
struct LINE{
LINE (int x, int y1, int y2, ll c) : x(x), y1(y1), y2(y2), c(c) {}
int x, y1, y2;
ll c;
bool operator <(const LINE &a)const{
return x<a.x;
}
};
vector<LINE> line;
void lazy(int idx, int s, int e, int l, int r, ll cost){
if(seg[idx].lazy!=0){
if(seg[idx].l==-1) {seg[idx].l = seg.size(); seg.push_back(ss);}
if(seg[idx].r==-1) {seg[idx].r = seg.size(); seg.push_back(ss);}
seg[seg[idx].l].lazy+=seg[idx].lazy; seg[seg[idx].l].mn += seg[idx].lazy;
seg[seg[idx].r].lazy+=seg[idx].lazy; seg[seg[idx].r].mn += seg[idx].lazy;
seg[idx].lazy = 0;
}
if(l<=s && e<=r){
seg[idx].lazy+=cost; seg[idx].mn+=cost; return;
}
if(e<l || s>r) return;
if(seg[idx].l==-1) {seg[idx].l = seg.size(); seg.push_back(ss);}
if(seg[idx].r==-1) {seg[idx].r = seg.size(); seg.push_back(ss);}
lazy(seg[idx].l, s, (s+e)/2, l, r, cost);
lazy(seg[idx].r, (s+e)/2+1, e, l, r, cost);
seg[idx].mn = min(seg[seg[idx].l].mn, seg[seg[idx].r].mn);
}
struct SEG2{
SEG2 (int l, int r, int lmn, int rmn, int smn, int mn, int lazy, int len) : l(l), r(r), lmn(lmn), rmn(rmn), smn(smn), mn(mn), lazy(lazy), len(len) {}
int l, r;
int lmn, rmn, smn;
int mn, lazy, len;
};
vector<SEG2> seg2;
vector<LINE> l1, l2;
void init(int idx, int s, int e){
seg2.push_back({-1, -1, e-s+1, e-s+1, e-s+1, 0, 0, e-s+1});
if(s==e) return;
seg2[idx].l=seg2.size();
init(seg2[idx].l, s, (s+e)/2);
seg2[idx].r=seg2.size();
init(seg2[idx].r, (s+e)/2+1, e);
}
void update(int idx, int s, int e, int l, int r, int c){
if(s!=e && seg2[idx].lazy!=0){
seg2[seg[idx].l].mn+=seg2[idx].lazy; seg2[seg2[idx].l].lazy+=seg2[idx].lazy;
seg2[seg[idx].r].mn+=seg2[idx].lazy; seg2[seg2[idx].r].lazy+=seg2[idx].lazy;
seg2[idx].lazy = 0;
}
if(l<=s && e<=r){
seg2[idx].lazy+=c; seg2[idx].mn+=c; return;
}
if(l>e || s>r) return;
update(seg2[idx].l, s, (s+e)/2, l, r, c);
update(seg2[idx].r, (s+e)/2+1, e, l, r, c);
if(seg2[seg2[idx].l].mn==seg2[seg2[idx].r].mn){
seg2[idx].mn = seg2[seg2[idx].l].mn;
seg2[idx].smn = max(seg2[seg2[idx].l].smn, max(seg2[seg2[idx].r].smn, seg2[seg2[idx].l].rmn+seg2[seg2[idx].r].lmn));
if(seg2[seg2[idx].l].lmn == seg2[seg2[idx].l].len) seg2[idx].lmn = seg2[seg2[idx].l].lmn + seg2[seg2[idx].r].lmn;
else seg2[idx].lmn = seg2[seg2[idx].l].lmn;
if(seg2[seg2[idx].r].rmn == seg2[seg2[idx].r].len) seg2[idx].rmn = seg2[seg2[idx].r].rmn + seg2[seg2[idx].l].rmn;
else seg2[idx].rmn = seg2[seg2[idx].r].rmn;
}else if(seg2[seg2[idx].l].mn<seg2[seg2[idx].r].mn){
seg2[idx].mn = seg2[seg2[idx].l].mn;
seg2[idx].smn = seg2[seg2[idx].l].smn;
seg2[idx].lmn = seg2[seg2[idx].l].lmn; seg2[idx].rmn = 0;
}else{
seg2[idx].mn = seg2[seg2[idx].r].mn;
seg2[idx].smn = seg2[seg2[idx].r].smn;
seg2[idx].lmn = 0; seg2[idx].rmn = seg2[seg2[idx].r].rmn;
}
return;
}
void solve(){
scanf("%d", &P);
for(int i=0; i<P; i++){
int a, b, c, d, e;
scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
l1.push_back({a, b, d, 1});
l2.push_back({c, b, d, -1});
}
sort(l1.begin(), l1.end()); sort(l2.begin(), l2.end());
init(0, 1, M);
int s = 1, e = 0;
int idx1 = 0, idx2 = 0;
int ans = 0;
while(e<=N){
int h = seg2[0].smn;
//printf("%d %d %d\n", s, e, h);
ans = max(ans, min(h, e-s+1));
if(h>=(e-s+1)){
e++;
while(idx1<l1.size() && l1[idx1].x==e){
update(0, 1, M, l1[idx1].y1, l1[idx1].y2, 1); idx1++;
}
}else{
while(idx2<l2.size() && l2[idx2].x==s){
//cout<<1<<endl;
update(0, 1, M, l2[idx2].y1, l2[idx2].y2, -1); idx2++;
}
s++;
}
}
printf("%d", ans);
return;
}
int main(){
scanf("%d%d", &N, &M);
scanf("%lld", &B);
if(B==0){
solve();
return 0;
}
N*=2; M*=2;
scanf("%d", &P);
for(int i=0; i<P; i++){
int a, b, c, d, e;
scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
a--; b--;
sc.push_back({a*2, c*2, b*2, d*2, (ll)e});
}
int s = 0, e = (min(N, M))/2, m;
while(s<e){
m = (s+e)/2+1;
seg.clear();
seg.push_back({-1, -1, 0, 0});
line.clear();
for(int i=0; i<sc.size(); i++){
SQ now = sc[i];
now.x1-=(m-1); now.y1-=(m-1); now.x2+=(m-1); now.y2+=(m-1);
line.push_back({max(m, now.x1), max(m, now.y1), min(M-m, now.y2), now.c});
line.push_back({max(m, now.x2), max(m, now.y1), min(M-m, now.y2), -now.c});
}
line.push_back({m, m, m, 0});
sort(line.begin(), line.end());
//printf("%d\n", m);
for(int i=0; i<line.size(); i++){
//printf("%d %d %d %lld\n", line[i].x, line[i].y1, line[i].y2, line[i].c);
if(line[i].x>N-m) break;
if(i!=0 && line[i].x!=line[i-1].x){
if(seg[0].mn<=B){
s = m; break;
}
}
lazy(0, m, M-m, line[i].y1, line[i].y2, line[i].c);
}
if(seg[0].mn<=B){
s = m;
}
if(s==m) continue;
else e = m-1;
}
printf("%d", s);
return 0;
}
Compilation message (stderr)
pyramid_base.cpp: In function 'void solve()':
pyramid_base.cpp:125:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(idx1<l1.size() && l1[idx1].x==e){
~~~~^~~~~~~~~~
pyramid_base.cpp:129:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(idx2<l2.size() && l2[idx2].x==s){
~~~~^~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:162:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<sc.size(); i++){
~^~~~~~~~~~
pyramid_base.cpp:171:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<line.size(); i++){
~^~~~~~~~~~~~
pyramid_base.cpp: In function 'void solve()':
pyramid_base.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &P);
~~~~~^~~~~~~~~~
pyramid_base.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
pyramid_base.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &B);
~~~~~^~~~~~~~~~~~
pyramid_base.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &P);
~~~~~^~~~~~~~~~
pyramid_base.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |