Submission #965590

#TimeUsernameProblemLanguageResultExecution timeMemory
965590idiotcomputerPyramid Base (IOI08_pyramid_base)C++11
42 / 100
5083 ms80972 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]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll b; int p; cin >> m >> n >> b >> p; 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]; 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; while (queue.size() > 0){ pii cur = queue.top(); queue.pop(); if (cur.f >= m) break; best = laz[0]+segtree[0]; if (best <= b && cur.f >= curr){ w = true; break; } 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...