Submission #253321

#TimeUsernameProblemLanguageResultExecution timeMemory
253321iefnah06Meetings (IOI18_meetings)C++11
0 / 100
73 ms71032 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; using ll = long long; struct line { int st, en; ll m, b; line() {} line(int st_, int en_, ll m_, ll b_) : st(st_), en(en_), m(m_), b(b_) {} ll eval(ll x){ return m * x + b; } }; vector<line> stuff; struct line_container { int st, en; ll lazy; line_container(int st_, int en_) : st(st_), en(en_), lazy(0) {} line front(){ assert(size()); line l = stuff[st]; l.b += lazy; return l; } line back(){ assert(size()); line l = stuff[en-1]; l.b += lazy; return l; } ll eval_front(ll x){ assert(size()); return lazy + stuff[st].eval(x); } ll eval_back(ll x){ assert(size()); return lazy + stuff[en-1].eval(x); } ll at(int p){ assert(size() > 0); int s = st, e = en; while(e - s > 1){ int mid = (s + e) / 2; if(stuff[mid].st <= p){ s = mid; } else { e = mid; } } assert(stuff[s].st <= p && p < stuff[s].en); return lazy + stuff[s].eval(p); } line pop_front(){ assert(size()); line l = stuff[st++]; l.b += lazy; return l; } line pop_back(){ assert(size()); line l = stuff[--en]; l.b += lazy; return l; } void push_back(line l){ l.b -= lazy; stuff[en++] = l; } void push_front(line l){ l.b -= lazy; stuff[--st] = l; } int size(){ return en-st; } }; int n; int qnum; vector<ll> ans; vector<int> heights, ql, qr; static const int S = 1 << 21; vector<pair<int, int> > seg; vector<vector<int> > queries; pair<int, int> max_query(int l, int r){ pair<int, int> res(0, -1); assert(max(0, l) < min(r, n)); for(int a = S+l, b = S+r; a < b; a /= 2, b /= 2){ if(a & 1){ res = max(res, seg[a]); a++; } if(b & 1){ --b; res = max(res, seg[b]); } } assert(res.first >= 1); return res; } line_container solve(int l, int r){ if(l >= r){ return line_container(l, l); } int x = -max_query(l, r).second; auto lcont = solve(l, x); auto rcont = solve(x+1, r); int cutoff = x+1; for(auto j : queries[x]){ assert(l <= ql[j] && qr[j] < r); ll a; if(x == qr[j]){ a = 0; } else if(x < qr[j]){ a = rcont.at(qr[j]); } else assert(false); ll cnd = ll(x - ql[j] + 1) * heights[x] + a; ans[j] = min(ans[j], cnd); } rcont.lazy += heights[x] * ll(x - l + 1); if(lcont.size()){ assert(lcont.back().en == x); ll lback = lcont.eval_back(x-1); while(rcont.size() > 0){ assert(lcont.size()); int st = rcont.front().st; int en = rcont.front().en; if(lback + (en - x) * ll(heights[x]) <= rcont.eval_front(en-1)){ cutoff = en; rcont.pop_front(); continue; } int s = st-1, e = en-1; while(e - s > 1){ int mid = (s + e) / 2; ll lval = lback + (mid - x + 1) * ll(heights[x]); ll rval = rcont.eval_front(mid); if(lval > rval){ e = mid; } else { s = mid; } } { vector<int> mode; for(int j = st; j < en; j++){ ll lval = lback + (j - x + 1) * ll(heights[x]); ll rval = rcont.eval_front(j); if(lval > rval) assert(j >= e); else assert(j < e); mode.push_back(lval > rval); } assert(is_sorted(mode.begin(), mode.end())); } assert(e < en && lback + (e - x + 1) * ll(heights[x]) > rcont.eval_front(e)); if(e > st){ assert(lback + ((e-1) - x + 1) * ll(heights[x]) <= rcont.eval_front(e-1)); } line bfront = rcont.pop_front(); bfront.st = e; rcont.push_front(bfront); cutoff = e; break; } assert(x < cutoff); lcont.push_back(line(x, cutoff, heights[x], lback - ll(x-1) * heights[x])); } else { lcont.push_back(line(x, x+1, heights[x], -ll(x-1) * heights[x])); } if(lcont.size() > rcont.size()){ while(rcont.size()){ lcont.push_back(rcont.pop_front()); } for(int j = lcont.st; j+1 < lcont.en; j++){ assert(stuff[j].en == stuff[j+1].st); } return lcont; } else { while(lcont.size()){ rcont.push_front(lcont.pop_back()); } for(int j = rcont.st; j+1 < rcont.en; j++){ assert(stuff[j].en == stuff[j+1].st); } return rcont; } } void solve(){ for(int i = 0; i < n; i++){ seg[S+i] = make_pair(heights[i], -i); } for(int i = S-1; i >= 1; i--){ seg[i] = max(seg[2*i], seg[2*i+1]); } for(int i = 0; i < n; i++) queries[i].clear(); for(int i = 0; i < qnum; i++){ assert(ql[i] <= qr[i]); if(ql[i] < qr[i]){ int x = -max_query(ql[i], qr[i]+1).second; queries[x].push_back(i); } } solve(0, n); } std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { heights = H; ql = L; qr = R; n = int(heights.size()); qnum = int(ql.size()); ans.assign(qnum, 1e18); seg.resize(2*S); queries.resize(n); stuff.resize(n); for(int i = 0; i < qnum; i++){ if(ql[i] == qr[i]){ ans[i] = heights[i]; } } for(int f = 0; f < 2; f++){ reverse(heights.begin(), heights.end()); for(int i = 0; i < qnum; i++){ ql[i] = n-1-ql[i]; qr[i] = n-1-qr[i]; swap(ql[i], qr[i]); } solve(); } return ans; }
#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...