Submission #1006218

#TimeUsernameProblemLanguageResultExecution timeMemory
1006218huutuanPyramid Base (IOI08_pyramid_base)C++14
100 / 100
4518 ms51284 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #include<bits/stdc++.h> using namespace std; struct Node{ int val, lazy; Node (int _val=0){ val=_val, lazy=0; } }; struct SegmentTree{ vector<Node> t; int n, h; void init(int _n){ n=_n; h=32-__builtin_clz(n); t.assign(2*n+1, Node()); } void apply(int k, int val){ t[k].val+=val; t[k].lazy+=val; } void build(int k){ while (k>1) k>>=1, t[k].val=min(t[k<<1].val, t[k<<1|1].val)+t[k].lazy; } void push(int k){ for (int s=h; s>0; --s){ int i=k>>s; if (t[i].lazy){ apply(i<<1, t[i].lazy); apply(i<<1|1, t[i].lazy); t[i].lazy=0; } } } void update(int l, int r, int val){ --l; l+=n; r+=n; int l0=l, r0=r; for (; l<r; l>>=1, r>>=1){ if (l&1) apply(l++, val); if (r&1) apply(--r, val); } build(l0); build(r0-1); } int get(int l, int r){ --l; l+=n; r+=n; push(l); push(r-1); int ans=INT_MAX; for (; l<r; l>>=1, r>>=1){ if (l&1) ans=min(ans, t[l++].val); if (r&1) ans=min(ans, t[--r].val); } return ans; } } st; struct Rect{ int x1, y1, x2, y2, z; Rect(){ x1=0, y1=0, x2=0, y2=0, z=0; } }; const int N=5e5+10; int m, n, p, q; Rect a[N], b[N]; pair<pair<int, int>, pair<int, int>> events[N*2]; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> p >> q >> m >> n; st.init(q); int l=1, r=min(p, q); for (int i=1; i<=n; ++i){ cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2 >> a[i].z; if (m==0){ r=min(r, max({a[i].x1-1, a[i].y1-1, p-a[i].x2, q-a[i].y2})); } } while (l<=r){ int mid=(l+r)>>1; int sz=0; for (int i=1; i<=n; ++i){ events[sz++]={{max(1, a[i].x1-mid+1), a[i].z}, {max(1, a[i].y1-mid+1), a[i].y2}}; events[sz++]={{a[i].x2+1, -a[i].z}, {max(1, a[i].y1-mid+1), a[i].y2}}; } sort(events, events+sz); bool check=0; for (int i=0; i<sz; ++i){ st.update(events[i].second.first, events[i].second.second, events[i].first.second); if (i==sz-1 || events[i].first.first!=events[i+1].first.first){ if (events[i].first.first+mid-1<=p){ check|=st.get(1, q-mid+1)<=m; } } } if (check) l=mid+1; else r=mid-1; } cout << r << '\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...