#include "meetings.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct line{
int a,b;
}a[750001];
vector <int32_t> ql,qr,ve[750001],v;
vector <int> h,res,ans;
set <int> s;
int n,q,mx[750001][20],lg[750001];
int f(int l, int r){
int d=lg[r-l+1],x=mx[l][d],y=mx[r-(1<<d)+1][d];
return (h[x]<h[y]?y:x);
}
int calc(int i){
int j=*s.lower_bound(i);
return a[j].a*i+a[j].b;
}
int dnc(int l, int r){
if (l>r)
return 0;
if (l==r){
a[l]={h[l],h[l]*(1-l)};
s.insert(l);
for (int i:ve[l])
if (qr[i]<=r)
ans[i]+=h[l];
return 0;
}
int mid=f(l,r);
int x=dnc(l,mid-1),y=dnc(mid+1,r)+h[mid]*(mid-l+1),c=(mid>l?calc(mid-1):0)+x+h[mid];
v.clear();
v.push_back(mid);
s.insert(mid);
int last=mid;
for (auto it=s.upper_bound(mid);it!=s.end()&&*it<=r;it++){
int i=*it;
if (h[mid]*i+c-h[mid]*mid<=a[i].a*i+a[i].b+y){
v.push_back(i);
last=i;
continue;
}
last=(a[i].b+y-c+h[mid]*mid)/(h[mid]-a[i].a);
break;
}
for (int i:v)
s.erase(i);
s.insert(last);
a[last]={h[mid],c-h[mid]*mid-y};
if (mid-l<r-mid+1){
for (int i=l;i<mid;i++)
a[i].b+=x-y;
for (int i:ve[l])
if (qr[i]>=mid&&qr[i]<=r)
ans[i]+=calc(qr[i])+y;
return y;
}
for (int i=mid;i<=r;i++)
a[i].b+=y-x;
for (int i:ve[l])
if (qr[i]>=mid&&qr[i]<=r)
ans[i]+=calc(qr[i])+x;
return x;
}
void solve(){
s.clear();
for (int j=1;j<20;j++)
for (int i=0;i+(1<<j)<=n;i++){
int l=mx[i][j-1],r=mx[i+(1<<(j-1))][j-1];
mx[i][j]=(h[l]<h[r]?r:l);
}
for (int i=0;i<n;i++)
ve[i].clear();
for (int i=0;i<q;i++){
int v=f(ql[i],qr[i]);
ans[i]=h[v]*(v-ql[i]+1);
if (v<qr[i])
ve[v+1].push_back(i);
}
dnc(0,n-1);
for (int i=0;i<q;i++)
res[i]=min(res[i],ans[i]);
}
vector <int> minimum_costs(vector <int32_t> H, vector <int32_t> L, vector <int32_t> R){
ql=L,qr=R,n=H.size(),q=L.size();
for (int i:H)
h.push_back(i);
res.assign(q,1e18);
for (int i=2;i<=n;i++)
lg[i]=lg[i/2]+1;
for (int i=0;i<n;i++)
mx[i][0]=i;
ans.assign(q,0);
solve();
reverse(h.begin(),h.end());
for (int i=0;i<q;i++){
ql[i]=n-ql[i]-1;
qr[i]=n-qr[i]-1;
swap(ql[i],qr[i]);
}
solve();
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
20828 KB |
Output is correct |
2 |
Correct |
7 ms |
23132 KB |
Output is correct |
3 |
Correct |
6 ms |
23132 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
8 ms |
23128 KB |
Output is correct |
6 |
Correct |
7 ms |
23420 KB |
Output is correct |
7 |
Correct |
7 ms |
23148 KB |
Output is correct |
8 |
Correct |
6 ms |
23388 KB |
Output is correct |
9 |
Correct |
6 ms |
23132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
20828 KB |
Output is correct |
2 |
Correct |
7 ms |
23132 KB |
Output is correct |
3 |
Correct |
6 ms |
23132 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
8 ms |
23128 KB |
Output is correct |
6 |
Correct |
7 ms |
23420 KB |
Output is correct |
7 |
Correct |
7 ms |
23148 KB |
Output is correct |
8 |
Correct |
6 ms |
23388 KB |
Output is correct |
9 |
Correct |
6 ms |
23132 KB |
Output is correct |
10 |
Correct |
10 ms |
23492 KB |
Output is correct |
11 |
Correct |
11 ms |
23640 KB |
Output is correct |
12 |
Correct |
10 ms |
23384 KB |
Output is correct |
13 |
Correct |
9 ms |
23388 KB |
Output is correct |
14 |
Correct |
10 ms |
23900 KB |
Output is correct |
15 |
Correct |
8 ms |
23388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
20828 KB |
Output is correct |
2 |
Correct |
26 ms |
27484 KB |
Output is correct |
3 |
Correct |
161 ms |
60872 KB |
Output is correct |
4 |
Correct |
96 ms |
51164 KB |
Output is correct |
5 |
Correct |
134 ms |
58820 KB |
Output is correct |
6 |
Correct |
116 ms |
61640 KB |
Output is correct |
7 |
Correct |
119 ms |
63832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
20828 KB |
Output is correct |
2 |
Correct |
26 ms |
27484 KB |
Output is correct |
3 |
Correct |
161 ms |
60872 KB |
Output is correct |
4 |
Correct |
96 ms |
51164 KB |
Output is correct |
5 |
Correct |
134 ms |
58820 KB |
Output is correct |
6 |
Correct |
116 ms |
61640 KB |
Output is correct |
7 |
Correct |
119 ms |
63832 KB |
Output is correct |
8 |
Correct |
156 ms |
53444 KB |
Output is correct |
9 |
Correct |
147 ms |
53340 KB |
Output is correct |
10 |
Correct |
144 ms |
53320 KB |
Output is correct |
11 |
Correct |
123 ms |
51156 KB |
Output is correct |
12 |
Correct |
115 ms |
51020 KB |
Output is correct |
13 |
Correct |
127 ms |
51420 KB |
Output is correct |
14 |
Correct |
163 ms |
61812 KB |
Output is correct |
15 |
Correct |
98 ms |
50888 KB |
Output is correct |
16 |
Correct |
112 ms |
59756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
20828 KB |
Output is correct |
2 |
Correct |
7 ms |
23132 KB |
Output is correct |
3 |
Correct |
6 ms |
23132 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
8 ms |
23128 KB |
Output is correct |
6 |
Correct |
7 ms |
23420 KB |
Output is correct |
7 |
Correct |
7 ms |
23148 KB |
Output is correct |
8 |
Correct |
6 ms |
23388 KB |
Output is correct |
9 |
Correct |
6 ms |
23132 KB |
Output is correct |
10 |
Correct |
10 ms |
23492 KB |
Output is correct |
11 |
Correct |
11 ms |
23640 KB |
Output is correct |
12 |
Correct |
10 ms |
23384 KB |
Output is correct |
13 |
Correct |
9 ms |
23388 KB |
Output is correct |
14 |
Correct |
10 ms |
23900 KB |
Output is correct |
15 |
Correct |
8 ms |
23388 KB |
Output is correct |
16 |
Correct |
4 ms |
20828 KB |
Output is correct |
17 |
Correct |
26 ms |
27484 KB |
Output is correct |
18 |
Correct |
161 ms |
60872 KB |
Output is correct |
19 |
Correct |
96 ms |
51164 KB |
Output is correct |
20 |
Correct |
134 ms |
58820 KB |
Output is correct |
21 |
Correct |
116 ms |
61640 KB |
Output is correct |
22 |
Correct |
119 ms |
63832 KB |
Output is correct |
23 |
Correct |
156 ms |
53444 KB |
Output is correct |
24 |
Correct |
147 ms |
53340 KB |
Output is correct |
25 |
Correct |
144 ms |
53320 KB |
Output is correct |
26 |
Correct |
123 ms |
51156 KB |
Output is correct |
27 |
Correct |
115 ms |
51020 KB |
Output is correct |
28 |
Correct |
127 ms |
51420 KB |
Output is correct |
29 |
Correct |
163 ms |
61812 KB |
Output is correct |
30 |
Correct |
98 ms |
50888 KB |
Output is correct |
31 |
Correct |
112 ms |
59756 KB |
Output is correct |
32 |
Correct |
1112 ms |
231160 KB |
Output is correct |
33 |
Correct |
975 ms |
235100 KB |
Output is correct |
34 |
Correct |
1185 ms |
231648 KB |
Output is correct |
35 |
Correct |
1286 ms |
233792 KB |
Output is correct |
36 |
Correct |
1039 ms |
232960 KB |
Output is correct |
37 |
Correct |
1269 ms |
232948 KB |
Output is correct |
38 |
Correct |
1979 ms |
311504 KB |
Output is correct |
39 |
Correct |
2346 ms |
319188 KB |
Output is correct |
40 |
Correct |
1761 ms |
262160 KB |
Output is correct |
41 |
Correct |
1841 ms |
382680 KB |
Output is correct |
42 |
Correct |
2007 ms |
383760 KB |
Output is correct |
43 |
Correct |
2128 ms |
384852 KB |
Output is correct |
44 |
Correct |
1900 ms |
307056 KB |
Output is correct |