이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |