Submission #588264

#TimeUsernameProblemLanguageResultExecution timeMemory
588264Bench0310Pyramid Base (IOI08_pyramid_base)C++17
100 / 100
1243 ms208180 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; namespace S1 { const int N=1000005; ll tree[4*N]; ll lazy[4*N]; void pull(int idx){tree[idx]=min(tree[2*idx],tree[2*idx+1]);} void apply(int idx,ll x){tree[idx]+=x; lazy[idx]+=x;} void push(int idx){for(int i=0;i<2;i++)apply(2*idx+i,lazy[idx]); lazy[idx]=0;} void update(int idx,int l,int r,int ql,int qr,int x) { if(ql>qr) return; if(l==ql&&r==qr) apply(idx,ll(x)); else { int m=(l+r)/2; push(idx); update(2*idx,l,m,ql,min(qr,m),x); update(2*idx+1,m+1,r,max(ql,m+1),qr,x); pull(idx); } } } namespace S2 { const int N=1000005; struct node { int sz; int mn,len; int lx,lc,rx,rc; int lazy; void ini(int s){sz=s; mn=lx=rx=0; len=lc=rc=s; lazy=0;} friend node merge(node &a,node &b) { node c; c.sz=a.sz+b.sz; c.mn=min(a.mn,b.mn); c.len=0; if(a.mn==c.mn) c.len=max(c.len,a.len); if(b.mn==c.mn) c.len=max(c.len,b.len); if(a.rx==c.mn&&b.lx==c.mn) c.len=max(c.len,a.rc+b.lc); c.lx=a.lx; c.lc=(a.lc<a.sz?a.lc:a.lc+(a.lx==b.lx)*b.lc); c.rx=b.rx; c.rc=(b.rc<b.sz?b.rc:b.rc+(a.rx==b.rx)*a.rc); c.lazy=0; return c; } void apply(int x){mn+=x; lx+=x; rx+=x; lazy+=x;} void push(node &a,node &b){a.apply(lazy); b.apply(lazy); lazy=0;} }; vector<node> tree(4*N); void build(int idx,int l,int r) { tree[idx].ini(r-l+1); if(l<r) { int m=(l+r)/2; build(2*idx,l,m); build(2*idx+1,m+1,r); } } void pull(int idx){tree[idx]=merge(tree[2*idx],tree[2*idx+1]);} void apply(int idx,int x){tree[idx].apply(x);} void push(int idx){tree[idx].push(tree[2*idx],tree[2*idx+1]);} void update(int idx,int l,int r,int ql,int qr,int x) { if(ql>qr) return; if(l==ql&&r==qr) apply(idx,x); else { int m=(l+r)/2; push(idx); update(2*idx,l,m,ql,min(qr,m),x); update(2*idx+1,m+1,r,max(ql,m+1),qr,x); pull(idx); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cin >> m >> n; int b,p; cin >> b >> p; vector<array<int,5>> obstacles(p); for(auto &[x1,y1,x2,y2,c]:obstacles) cin >> x1 >> y1 >> x2 >> y2 >> c; if(b>0) { using namespace S1; int l=0,r=min(n,m)+1; vector<array<int,3>> v[m+2]; while(l<r-1) { int len=(l+r)/2; bool ok=0; int limm=m-len+1; int limn=n-len+1; auto add=[&](int x1,int y1,int x2,int y2,int c) { v[x1].push_back({y1,y2,c}); v[x2+1].push_back({y1,y2,-c}); }; for(auto [x1,y1,x2,y2,c]:obstacles) add(max(1,x1-len+1),max(1,y1-len+1),min(x2,limm),min(y2,limn),c); for(int x=1;x<=limm+1;x++) { for(auto [y1,y2,c]:v[x]) update(1,1,limn,y1,y2,c); if(x<=limm) ok|=(tree[1]<=b); v[x].clear(); } if(ok) l=len; else r=len; } cout << l << "\n"; } else { using namespace S2; int res=0; build(1,1,n); auto f=[&]()->int{return (tree[1].mn==0)*tree[1].len;}; vector<array<int,2>> l[m+1],r[m+1]; for(auto [x1,y1,x2,y2,c]:obstacles) { l[x1].push_back({y1,y2}); r[x2].push_back({y1,y2}); } int g=0; for(int i=1;i<=m;i++) { while(f()>=g-i+1) { res=max(res,g-i+1); if(g==m) break; g++; for(auto [y1,y2]:l[g]) update(1,1,n,y1,y2,1); } for(auto [y1,y2]:r[i]) update(1,1,n,y1,y2,-1); } cout << res << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...