#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())
#define pb(x) push_back(x);
#define pp() pop_back();
#define lc 2*id+0
#define rc 2*id+1
const int LC = 1e6+2, L = 4e5+2;
const ll inf = 1e10;
int n,m,p,b;
vector<ppi> add[LC],er[LC];
random_device device;
default_random_engine rng(device());
#define randt(a,b) uniform_int_distribution<int64_t>(a,b)(rng)
void pr(int* vv,int l,int r){for(int i=l;i<r;i++){cout<<vv[i]<<" ";}cout<<endl;}
void prv(vector<int> vv){for(auto i:vv){cout<<i<<" ";}cout<<endl;}
void prl(long long* vv,int l,int r){for(int i=l;i<r;i++){cout<<vv[i]<<" ";}cout<<endl;}
void prvl(vector<long long> vv){for(auto i:vv){cout<<i<<" ";}cout<<endl;}
void prp(pii* vv,int l,int r){for(int i=l;i<r;i++){cout<<i<<": "<<vv[i].f<<" , "<<vv[i].s<<" / ";}cout<<endl;}
struct node{
ll lazy, mn;
node(){
lazy = mn = 0;
}
}t[LC*6];
struct sagi{
inline void spread(int id){
t[lc].lazy += t[id].lazy;
t[rc].lazy += t[id].lazy;
t[id].mn += t[id].lazy;
t[id].lazy = 0;
}
inline void update(int id,int l,int r,int l2,int r2,ll x){
spread(id);
if(l==l2 and r==r2){
t[id].lazy += x;
return;
}
int mid = (l2+r2)>>1;
if(l<mid)
update(lc,l,min(r,mid),l2,mid,x);
if(r>mid)
update(rc,max(l,mid),r,mid,r2,x);
spread(lc);
spread(rc);
t[id].mn = min(t[lc].mn, t[rc].mn);
}
inline ll get(int id,int l,int r,int l2,int r2){
spread(id);
if(l==l2 and r==r2){
return t[id].mn;
}
int mid = (l2+r2)>>1;
ll ans = inf;
if(l<mid)
ans = min(ans, get(lc,l,min(r,mid),l2,mid));
if(r>mid)
ans = min(ans, get(rc,max(l,mid),r,mid,r2));
return ans;
}
};
int main(){
//ofstream cout ("out.txt");
//ifstream cin ("in.txt");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
scanf("%d %d",&n,&m);
scanf("%d",&b);
scanf("%d",&p);
for(int i=0;i<p;i++){
int x1,y1,x2,y2,pr;
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&pr);
ppi x = ppi(pii(y1,y2),pr);
add[x1].pb(x);
er[x2].pb(x);
}
int l=0,r=1e6+1;
while(r-l>1){
int mid = (l+r)>>1;
if(mid > n or mid > m){
r = mid;
continue;
}
sagi seg;
for(int i=1;i<LC*6;i++){
t[i].lazy = t[i].mn = 0;
}
seg.update(1,1,mid,1,m+1,inf);
ll ans = inf;
for(int i=1;i<=n;i++){
if(i>mid){
ans = min(ans,t[1].mn);
}
for(auto j:add[i]){
seg.update(1,max(j.f.f,mid),min(j.f.s+mid,m+1),1,m+1,j.s);
}
for(auto j:er[max(i-mid,0)]){
seg.update(1,max(j.f.f,mid),min(j.f.s+mid,m+1),1,m+1,-j.s);
}
if(i>mid){
ans = min(ans,t[1].mn);
}
}
if(ans <= b)
l = mid;
else
r = mid;
}
cout<<l;
}
Compilation message
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%d %d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d",&b);
| ~~~~~^~~~~~~~~
pyramid_base.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | scanf("%d",&p);
| ~~~~~^~~~~~~~~
pyramid_base.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&pr);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
81 ms |
141184 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
141140 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
110 ms |
141260 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
133 ms |
141392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
162 ms |
141416 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
229 ms |
141400 KB |
Output is correct |
| 2 |
Correct |
239 ms |
141392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
262 ms |
141396 KB |
Output is correct |
| 2 |
Correct |
233 ms |
141396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
118 ms |
141648 KB |
Output is correct |
| 2 |
Correct |
168 ms |
141700 KB |
Output is correct |
| 3 |
Correct |
163 ms |
141580 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
308 ms |
142392 KB |
Output is correct |
| 2 |
Correct |
375 ms |
142420 KB |
Output is correct |
| 3 |
Correct |
342 ms |
142504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
486 ms |
142932 KB |
Output is correct |
| 2 |
Correct |
115 ms |
142932 KB |
Output is correct |
| 3 |
Incorrect |
173 ms |
142512 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
679 ms |
143440 KB |
Output is correct |
| 2 |
Correct |
837 ms |
143188 KB |
Output is correct |
| 3 |
Correct |
416 ms |
143648 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
629 ms |
143912 KB |
Output is correct |
| 2 |
Correct |
1284 ms |
143844 KB |
Output is correct |
| 3 |
Correct |
1216 ms |
143776 KB |
Output is correct |
| 4 |
Correct |
1103 ms |
144172 KB |
Output is correct |
| 5 |
Correct |
1177 ms |
143696 KB |
Output is correct |
| 6 |
Correct |
426 ms |
144124 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5053 ms |
158292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5050 ms |
166456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5066 ms |
173996 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
