Submission #965592

#TimeUsernameProblemLanguageResultExecution timeMemory
965592idiotcomputerPyramid Base (IOI08_pyramid_base)C++11
90 / 100
5042 ms49764 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<ll,ll> #define f first #define s second #define ll long long int const int mxP = 4e5; const int mxN = 1e6; int n,m; ll segtree[4*mxN+1]; ll laz[4*mxN+1]; int curr; void build(int l = 0, int r = n-1, int idx = 0){ if (r+1<curr){ segtree[idx] = 2e9+1; laz[idx] = 0; return; } segtree[idx] = 0; laz[idx] = 0; if (l == r) return; int m = (l+r)/2; build(l,m,2*idx+1); build(m+1,r,2*idx+2); } void upd(int tl, int tr, ll v, int l = 0, int r = n-1, int idx = 0){ if (l > tr || r < tl || r+1<curr) return; if (l >= tl && r <= tr){ laz[idx] += v; return; } int m = (l+r)/2; upd(tl,tr,v,l,m,2*idx+1); upd(tl,tr,v,m+1,r,2*idx+2); segtree[idx] = min(segtree[2*idx+1]+laz[2*idx+1],segtree[2*idx+2]+laz[2*idx+2]); } void build1(int l = 0, int r = n-1, int idx = 0){ if (r+1<curr){ segtree[idx] = m+1; laz[idx] = m+1; return; } segtree[idx] = 0; laz[idx] = 0; if (l == r) return; int m = (l+r)/2; build1(l,m,2*idx+1); build1(m+1,r,2*idx+2); } void upd1(int tl, int tr, ll v, int l = 0, int r = n-1, int idx = 0){ if (l > tr || r < tl || r+1<curr) return; if (l >= tl && r <= tr){ laz[idx] = max(laz[idx],v); return; } laz[2*idx+1] = max(laz[idx],laz[2*idx+1]); laz[2*idx+2] = max(laz[idx],laz[2*idx+2]); laz[idx] = 0; int m = (l+r)/2; upd1(tl,tr,v,l,m,2*idx+1); upd1(tl,tr,v,m+1,r,2*idx+2); segtree[idx] = min(max(segtree[2*idx+1],laz[2*idx+1]),max(segtree[2*idx+2],laz[2*idx+2])); } void solve(int b, int p){ int r[p]; pii y[p]; vector<pii> vals(p); int x1,y1,x2,y2,c1; for (int i =0; i < p; i++){ cin >> x1 >> y1 >> x2 >> y2 >> c1; x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1; r[i] = x2; y[i] = {y1,y2}; vals[i] = {x1,i}; } sort(vals.begin(),vals.end()); int start = 0; int end = min(n,m)+1; bool w; int best; while (end - start > 1){ curr = (start+end)/2; build1(); w = false; for (int i = 0; i < p; i++){ best = max(laz[0],segtree[0]); if (vals[i].f-best >= curr){ w = true; break; } upd1(y[vals[i].s].f,min((ll) n-1,y[vals[i].s].s+curr-1),r[vals[i].s]+1); } best = max(laz[0],segtree[0]); if (m-best >= curr) w = true; if (w) start = curr; else end = curr; } cout << start << "\n"; return; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll b; int p; cin >> m >> n >> b >> p; if (b == 0){ solve(b,p); return 0; } pii x[p]; pii y[p]; ll c[p]; ll x1,y1,x2,y2,c1; for (int i =0; i < p; i++){ cin >> x1 >> y1 >> x2 >> y2 >> c1; x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1; x[i] = {x1,x2}; y[i] = {y1,y2}; c[i] = c1; } int start = 0; int end = min(n,m)+1; bool w; ll best; bool vis[p]; int last; while (end - start > 1){ curr = (start+end)/2; build(); memset(vis,0,sizeof(vis)); priority_queue<pii, vector<pii>, greater<pii>> queue; for (int i = 0; i < p; i++){ queue.push({x[i].f,i}); queue.push({x[i].s+curr,i}); } w = false; last = -1; while (queue.size() > 0){ pii cur = queue.top(); queue.pop(); if (cur.f >= m) break; best = laz[0]+segtree[0]; if (last != cur.f && best <= b && cur.f >= curr){ w = true; break; } last = cur.f; ll val = c[cur.s]; if (vis[cur.s]) val *= -1; else vis[cur.s] = 1; upd(y[cur.s].f,min((ll) n-1,y[cur.s].s+curr-1),val); } best = laz[0]+segtree[0]; if (best <= b) w = true; if (w) start = curr; else end = curr; } cout << start << "\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...