Submission #1006176

#TimeUsernameProblemLanguageResultExecution timeMemory
1006176huutuanPyramid Base (IOI08_pyramid_base)C++14
80 / 100
5037 ms81996 KiB
#include<bits/stdc++.h> using namespace std; // #define int long long struct Node{ int val, lazy; Node (int _val=0){ val=_val, lazy=0; } void merge(const Node &tl, const Node &tr){ val=min(tl.val, tr.val); } }; struct SegmentTree{ vector<Node> t; int n; void init(int _n){ n=_n; t.assign(4*n+1, Node()); } void apply(int k, int val){ t[k].val+=val; t[k].lazy+=val; } void push(int k){ if (t[k].lazy){ apply(k<<1, t[k].lazy); apply(k<<1|1, t[k].lazy); t[k].lazy=0; } } void update(int k, int l, int r, int L, int R, int val){ if (r<L || R<l) return; if (L<=l && r<=R){ apply(k, val); return; } push(k); int mid=(l+r)>>1; update(k<<1, l, mid, L, R, val); update(k<<1|1, mid+1, r, L, R, val); t[k].merge(t[k<<1], t[k<<1|1]); } int get(int k, int l, int r, int L, int R){ if (r<L || R<l) return 1e18; if (L<=l && r<=R) return t[k].val; push(k); int mid=(l+r)>>1; return min(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R)); } } 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]; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> p >> q >> m >> n; st.init(q); for (int i=1; i<=n; ++i) cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2 >> a[i].z; int l=1, r=min(p, q); while (l<=r){ int mid=(l+r)>>1; vector<pair<pair<int, int>, pair<int, int>>> events; for (int i=1; i<=n; ++i){ events.push_back({{max(1, a[i].x1-mid+1), a[i].z}, {max(1, a[i].y1-mid+1), a[i].y2}}); events.push_back({{a[i].x2+1, -a[i].z}, {max(1, a[i].y1-mid+1), a[i].y2}}); } sort(events.begin(), events.end()); bool check=0; for (int i=0; i<(int)events.size(); ++i){ st.update(1, 1, q, events[i].second.first, events[i].second.second, events[i].first.second); if (i==(int)events.size()-1 || events[i].first.first!=events[i+1].first.first){ if (events[i].first.first+mid-1<=p){ check|=st.get(1, 1, q, 1, q-mid+1)<=m; } } } if (check) l=mid+1; else r=mid-1; } cout << r << '\n'; return 0; }

Compilation message (stderr)

pyramid_base.cpp: In member function 'int SegmentTree::get(int, int, int, int, int)':
pyramid_base.cpp:48:30: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   48 |       if (r<L || R<l) return 1e18;
      |                              ^~~~
#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...