Submission #807018

#TimeUsernameProblemLanguageResultExecution timeMemory
807018fatemetmhrMeetings (IOI18_meetings)C++17
60 / 100
2298 ms786432 KiB
// Be name khode // #include "meetings.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define mp make_pair #define fi first #define se second #define pb push_back typedef long long ll; const int maxn5 = 75e4 + 5; const int maxnt = 3e6 + 5; const int lg = 20; const ll inf = 1e18; int n; vector <ll> ret; ll a[maxn5]; namespace rmq{ pair <int, int> mx[lg][maxn5]; void build(int n){ for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++) mx[i][j] = max(mx[i - 1][j], (j + (1 << (i - 1))) < n ? mx[i - 1][j + (1 << (i - 1))] : mp(-1, -1)); } int get_max(int l, int r){ int k = 31 - __builtin_clz(r - l + 1); return max(mx[k][l], mx[k][r - (1 << k) + 1]).se; } } struct cht{ vector <pair<ll, pair<ll, ll>>> av; // {st, {cons, shib}} cht(){ av.clear(); } ll inter(pair <ll, ll> a, pair <ll, ll> b){ if(a.se == b.se) return a.fi > b.fi ? inf : -inf; //cout << a.fi << ' ' << a.se << ' ' << b.fi << ' ' << b.se << endl; return (a.fi - b.fi) / (b.se - a.se) + ((a.fi - b.fi) % (b.se - a.se) > 0); } void add(ll cons, ll sh){ ll st = -inf; while(av.size() && (st = inter(av.back().se, mp(cons, sh))) <= av.back().fi) av.pop_back(); if(av.empty()) st = -inf; //cout << "ha? " << cons << ' ' << sh << ' ' << st << ' ' << av.size() << endl; //cout << (-122) / 46 << endl; av.pb({st, {cons, sh}}); } ll get(ll x){ if(av.empty()) return -inf; int pt = upper_bound(all(av), mp(x, mp(inf, inf))) - av.begin() - 1; //cout << "we all gor " << pt << ' ' << av[pt].se.fi << ' ' << av[pt].se.se << ' ' << av.size() << endl; //cout << av.back().fi << ' ' << x << endl; //cout << av.back().se.fi << ' ' << av.back().se.se << endl; return av[pt].se.fi + av[pt].se.se * x; } }; struct segment{ ll lazy[maxnt]; cht seg[maxnt]; segment(){ memset(lazy, 0, sizeof lazy); } void build(int l, int r, int v){ if(r - l == 1){ seg[v].add(0, 0); return; } int mid = (l + r) >> 1; build(l, mid, v * 2); build(mid, r, v * 2 + 1); } void add_cht(int l, int r, int lq, int rq, pair <ll, ll> val, int v){ if(rq <= l || r <= lq) return; //cout << "there's " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << val.fi << ' ' << val.se << ' ' << v << ' ' << lazy[v] << endl; val.fi += lazy[v]; if(lq <= l && r <= rq){ ////cout << "baba " << val.fi << ' ' << val.se << endl; seg[v].add(val.fi, val.se); return; } int mid = (l + r) >> 1; add_cht(l, mid, lq, rq, val, v * 2); add_cht(mid, r, lq, rq, val, v * 2 + 1); } void add(int l, int r, int lq, int rq, ll val, int v){ if(rq <= l || r <= lq) return; //cout << "adding " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << val << ' ' << v << endl; if(lq <= l && r <= rq){ lazy[v] += val; return; } int mid = (l + r) >> 1; add(l, mid, lq, rq, val, v * 2); add(mid, r, lq, rq, val, v * 2 + 1); } ll get(int l, int r, int id, int v){ ll ret = (-seg[v].get(id)) + lazy[v]; //cout << "look " << l << ' ' << r << ' ' << v << ' ' << ret << ' ' << lazy[v] << ' ' << id << endl; if(r - l == 1) return ret; int mid = (l + r) >> 1; if(abs(id) < mid) ret = min(ret, get(l, mid, id, v * 2) + lazy[v]); else ret = min(ret, get(mid, r, id, v * 2 + 1) + lazy[v]); //cout << "fina " << l << ' ' << r << ' ' << ret << ' ' << lazy[v] << endl; return ret; } } pre, suf; vector <pair<pair<int, int>, int>> req[maxn5]; void cartesian(int l, int r){ if(r - l == 1){ for(auto [p, id] : req[l]) ret[id] = a[l]; pre.add(0, n, l, l + 1, a[l], 1); suf.add(0, n, l, l + 1, a[l], 1); return; } int mx = rmq::get_max(l, r - 1); if(l < mx) cartesian(l, mx); if(mx + 1 < r) cartesian(mx + 1, r); //cout << "in " << l << ' ' << r << ' ' << mx << endl; for(auto [p, id] : req[mx]){ int lq = p.fi, rq = p.se; ret[id] = (rq - lq + 1) * a[mx]; //cout << ret[id] << endl; if(lq < mx) ret[id] = min(ret[id], suf.get(0, n, lq, 1) + (rq - mx + 1) * a[mx]); //cout << ret[id] << endl; if(rq > mx) ret[id] = min(ret[id], pre.get(0, n, -rq, 1) + (mx - lq + 1) * a[mx]); //cout << ret[id] << endl; } ll keeppre = (l < mx ? pre.get(0, n, -(mx - 1), 1) : 0); ll keepsuf = (mx + 1 < r ? suf.get(0, n, mx + 1, 1) : 0); //cout << "in " << l << ' ' << r << ' ' << mx << ' ' << keepsuf << ' ' << keeppre << endl; pre.add(0, n, mx, r, (mx - l + 1) * a[mx], 1); suf.add(0, n, l, mx + 1, (r - mx) * a[mx], 1); pre.add_cht(0, n, mx, r, mp(-(keeppre + (1 - mx) * a[mx]), a[mx]), 1); //cout << "all here " << endl; suf.add_cht(0, n, l, mx + 1, mp(-(keepsuf + (1 + mx) * a[mx]), a[mx]), 1); } std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l, std::vector<int> r) { n = h.size(); for(int i = 0; i < n; i++) a[i] = h[i]; int q = l.size(); ret.resize(q); for(int i = 0; i < n; i++) rmq::mx[0][i] = mp(h[i], i); rmq::build(n); for(int i = 0; i < q; i++){ int mx = rmq::get_max(l[i], r[i]); req[mx].pb({{l[i], r[i]}, i}); } pre.build(0, n, 1); suf.build(0, n, 1); cartesian(0, n); return ret; }
#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...