#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;
vector<pair<int, int> > key;
static const int S = 1 << 21;
vector<pair<pair<int, int>, int> > seg;
vector<vector<int> > queries;
pair<pair<int, int>, int> max_query(int l, int r){
pair<pair<int, int>, int> res(make_pair(0, -1), -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]);
}
}
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;
}
}
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());
}
return lcont;
} else {
while(lcont.size()){
rcont.push_front(lcont.pop_back());
}
return rcont;
}
}
void solve(){
for(int i = 0; i < n; i++){
seg[S+i] = make_pair(key[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[ql[i]];
}
}
key.resize(n);
for(int i = 0; i < n; i++){
key[i] = make_pair(heights[i], i);
}
for(int f = 0; f < 2; f++){
solve();
reverse(heights.begin(), heights.end());
reverse(key.begin(), key.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]);
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
49660 KB |
Output is correct |
2 |
Correct |
49 ms |
49784 KB |
Output is correct |
3 |
Correct |
49 ms |
49784 KB |
Output is correct |
4 |
Correct |
49 ms |
49784 KB |
Output is correct |
5 |
Correct |
44 ms |
49784 KB |
Output is correct |
6 |
Correct |
55 ms |
50048 KB |
Output is correct |
7 |
Correct |
45 ms |
49756 KB |
Output is correct |
8 |
Correct |
42 ms |
50296 KB |
Output is correct |
9 |
Correct |
42 ms |
49912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
49660 KB |
Output is correct |
2 |
Correct |
49 ms |
49784 KB |
Output is correct |
3 |
Correct |
49 ms |
49784 KB |
Output is correct |
4 |
Correct |
49 ms |
49784 KB |
Output is correct |
5 |
Correct |
44 ms |
49784 KB |
Output is correct |
6 |
Correct |
55 ms |
50048 KB |
Output is correct |
7 |
Correct |
45 ms |
49756 KB |
Output is correct |
8 |
Correct |
42 ms |
50296 KB |
Output is correct |
9 |
Correct |
42 ms |
49912 KB |
Output is correct |
10 |
Correct |
47 ms |
50296 KB |
Output is correct |
11 |
Correct |
50 ms |
50424 KB |
Output is correct |
12 |
Correct |
55 ms |
50296 KB |
Output is correct |
13 |
Correct |
49 ms |
50424 KB |
Output is correct |
14 |
Correct |
55 ms |
50808 KB |
Output is correct |
15 |
Correct |
48 ms |
50296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
49624 KB |
Output is correct |
2 |
Correct |
99 ms |
53368 KB |
Output is correct |
3 |
Correct |
238 ms |
72096 KB |
Output is correct |
4 |
Correct |
192 ms |
63524 KB |
Output is correct |
5 |
Correct |
147 ms |
70136 KB |
Output is correct |
6 |
Correct |
205 ms |
74232 KB |
Output is correct |
7 |
Correct |
236 ms |
76540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
49624 KB |
Output is correct |
2 |
Correct |
99 ms |
53368 KB |
Output is correct |
3 |
Correct |
238 ms |
72096 KB |
Output is correct |
4 |
Correct |
192 ms |
63524 KB |
Output is correct |
5 |
Correct |
147 ms |
70136 KB |
Output is correct |
6 |
Correct |
205 ms |
74232 KB |
Output is correct |
7 |
Correct |
236 ms |
76540 KB |
Output is correct |
8 |
Correct |
202 ms |
64252 KB |
Output is correct |
9 |
Correct |
181 ms |
63992 KB |
Output is correct |
10 |
Correct |
179 ms |
64216 KB |
Output is correct |
11 |
Correct |
191 ms |
63420 KB |
Output is correct |
12 |
Correct |
164 ms |
63224 KB |
Output is correct |
13 |
Correct |
170 ms |
63608 KB |
Output is correct |
14 |
Correct |
201 ms |
72568 KB |
Output is correct |
15 |
Correct |
175 ms |
63356 KB |
Output is correct |
16 |
Correct |
226 ms |
72824 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
49660 KB |
Output is correct |
2 |
Correct |
49 ms |
49784 KB |
Output is correct |
3 |
Correct |
49 ms |
49784 KB |
Output is correct |
4 |
Correct |
49 ms |
49784 KB |
Output is correct |
5 |
Correct |
44 ms |
49784 KB |
Output is correct |
6 |
Correct |
55 ms |
50048 KB |
Output is correct |
7 |
Correct |
45 ms |
49756 KB |
Output is correct |
8 |
Correct |
42 ms |
50296 KB |
Output is correct |
9 |
Correct |
42 ms |
49912 KB |
Output is correct |
10 |
Correct |
47 ms |
50296 KB |
Output is correct |
11 |
Correct |
50 ms |
50424 KB |
Output is correct |
12 |
Correct |
55 ms |
50296 KB |
Output is correct |
13 |
Correct |
49 ms |
50424 KB |
Output is correct |
14 |
Correct |
55 ms |
50808 KB |
Output is correct |
15 |
Correct |
48 ms |
50296 KB |
Output is correct |
16 |
Correct |
45 ms |
49624 KB |
Output is correct |
17 |
Correct |
99 ms |
53368 KB |
Output is correct |
18 |
Correct |
238 ms |
72096 KB |
Output is correct |
19 |
Correct |
192 ms |
63524 KB |
Output is correct |
20 |
Correct |
147 ms |
70136 KB |
Output is correct |
21 |
Correct |
205 ms |
74232 KB |
Output is correct |
22 |
Correct |
236 ms |
76540 KB |
Output is correct |
23 |
Correct |
202 ms |
64252 KB |
Output is correct |
24 |
Correct |
181 ms |
63992 KB |
Output is correct |
25 |
Correct |
179 ms |
64216 KB |
Output is correct |
26 |
Correct |
191 ms |
63420 KB |
Output is correct |
27 |
Correct |
164 ms |
63224 KB |
Output is correct |
28 |
Correct |
170 ms |
63608 KB |
Output is correct |
29 |
Correct |
201 ms |
72568 KB |
Output is correct |
30 |
Correct |
175 ms |
63356 KB |
Output is correct |
31 |
Correct |
226 ms |
72824 KB |
Output is correct |
32 |
Correct |
1434 ms |
158328 KB |
Output is correct |
33 |
Correct |
1062 ms |
156832 KB |
Output is correct |
34 |
Correct |
1463 ms |
158732 KB |
Output is correct |
35 |
Correct |
1551 ms |
159640 KB |
Output is correct |
36 |
Correct |
1081 ms |
159608 KB |
Output is correct |
37 |
Correct |
1366 ms |
158988 KB |
Output is correct |
38 |
Correct |
1857 ms |
228492 KB |
Output is correct |
39 |
Correct |
1868 ms |
228368 KB |
Output is correct |
40 |
Correct |
1567 ms |
167056 KB |
Output is correct |
41 |
Correct |
2275 ms |
284424 KB |
Output is correct |
42 |
Correct |
3196 ms |
285780 KB |
Output is correct |
43 |
Correct |
2759 ms |
285456 KB |
Output is correct |
44 |
Correct |
2159 ms |
227812 KB |
Output is correct |