#include "meetings.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define ef emplace_front
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
const ld EPS = 1e-8;
ll operator * (const pll &a, const pll &b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll &a, const pll &b, const pll &c) { return a*b + b*c + c*a; }
ll lnef(ll a, ll b, ll x) { return a*x + b; }
const int MAXN = 750055;
const int MAXQ = 750055;
const int MX = 1048576;
struct MNSEG {
int d[MX*2];
void init(int dt[], int n) {
for(int i = 0; i < n; i++)
d[i+MX] = dt[i];
fill(d+MX+n, d+MX*2, INF);
for(int i = MX; --i;)
d[i] = min(d[i<<1], d[i<<1|1]);
}
int get(int s, int e) {
int r = INF; for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
if(s&1) { upmin(r, d[s]); s++; }
if(~e&1) { upmin(r, d[e]); e--; }
}
return r;
}
} mnseg;
struct NOD {
int s, e, m, l, r;
} nod[MAXN*2]; int nodN;
vector<int> XQV[MAXN];
int nodXI[MAXN];
pil arr[MAXN*8];
struct DEQ {
int s, e, __s;
void set(int __s) { s = e = __s*2; this->__s = __s; }
bool empty() { return s == e; }
pil& front() { return arr[s]; }
pil& back() { return arr[e-1]; }
pil& operator [] (const unsigned int a) { return arr[s+a]; }
void pop_front() { s++; }
void pop_back() { e--; }
void emplace_back(const int &a, const ll &b) { arr[e++] = pil(a, b); }
void emplace_back(const pil& p) { arr[e++] = p; }
void emplace_front(const int &a, const ll &b) { arr[--s] = pil(a, b); }
void emplace_front(const pil& p) { arr[--s] = p; }
void clear() { set(__s); }
unsigned int size() { return e-s; }
};
struct CHN {
DEQ CH;
ll delta;
int s, e;
void set(int __s, int __e) { CH.set(__s+MAXN); }
void cut(ll a, ll b) {
ll startY = lnef(a, b, s);
ll endY = lnef(a, b, e);
if(CH[0].second + delta < startY) return;
if(endY <= CH.back().second + delta) {
delta = 0;
CH.clear();
CH.eb(s, startY);
if(s != e) CH.eb(e, endY);
return;
}
int t = 0, n = sz(CH);
for(; t+1 < n && lnef(a, b, CH[t+1].first) <= CH[t+1].second + delta; t++);
ll c = (CH[t+1].second - CH[t].second) / (CH[t+1].first - CH[t].first);
ll d = CH[t].second + delta - c * CH[t].first;
int X = ld(d-b) / (a-c) + EPS;
for(; (a-c) * (X+1) <= d-b; X++);
for(; (a-c) * (X-1) >= d-b; X--);
ll Y = lnef(a, b, X);
for(int i = 0; i <= t; i++) CH.pop_front();
if(Y < lnef(c, d, X) && X+1 < CH[0].first) CH.ef(X+1, lnef(c, d, X+1) - delta);
if(s < X && X < CH[0].first) CH.ef(X, Y - delta);
if(s < CH[0].first) CH.ef(s, startY - delta);
}
void mergeback(CHN &v) {
ll dt = -delta + v.delta;
for(int i = 0, n = sz(v.CH); i < n; i++)
CH.eb(v.CH[i].first, v.CH[i].second + dt);
e = v.e;
}
void mergefront(CHN &v) {
ll dt = -delta + v.delta;
for(int i = sz(v.CH); i--;)
CH.ef(v.CH[i].first, v.CH[i].second + dt);
s = v.s;
}
ll get(int X) {
if(s == e) return CH[0].second + delta;
int ls = 0, le = sz(CH)-2; for(int m; ls < le;) {
m = (ls + le + 1) >> 1;
if(CH[m].first <= X && X <= CH[m+1].first) {
ls = m;
break;
}
if(X < CH[m].first) le = m-1;
else ls = m;
}
ll a = (CH[ls+1].second - CH[ls].second) / (CH[ls+1].first - CH[ls].first);
ll b = CH[ls].second + delta - a * CH[ls].first;
return lnef(a, b, X);
}
};
int H[MAXN], HO[MAXN], HRO[MAXN];
int A[MAXQ], B[MAXQ], C[MAXQ];
int QS[MAXQ], QE[MAXQ];
ll Ans[MAXQ], preAns[MAXQ];
int N, Q;
int makeTree(int s, int e) {
nodN++; int idx = nodN;
if(!nodXI[s]) nodXI[s] = idx;
nod[idx].s = s;
nod[idx].e = e;
if(s == e) return idx;
nod[idx].m = HO[mnseg.get(s+1, e)];
nod[idx].l = makeTree(s, nod[idx].m-1);
nod[idx].r = makeTree(nod[idx].m, e);
return idx;
}
void makeTree() {
nodN = 0;
fill(nodXI, nodXI+MAXN, 0);
for(int i = 0; i < MAXN; i++) XQV[i].clear();
for(int i = 1; i <= Q; i++) XQV[QS[i]].eb(i);
makeTree(0, N);
}
void calTree(CHN &chn, int idx) {
auto &v = nod[idx];
chn.set(v.s, v.e);
if(v.s == v.e) {
chn.CH.eb(v.s, H[v.s]);
chn.delta = 0;
chn.s = v.s;
chn.e = v.e;
} else {
CHN chnR;
calTree(chn, v.l);
calTree(chnR, v.r);
chnR.delta += H[v.s] + ll(v.m - v.s - 1) * H[v.m];
chnR.cut(H[v.m], chn.CH.back().second + chn.delta + ll(-v.m + 1) * H[v.m]);
if(sz(chn.CH) < sz(chnR.CH)) {
chnR.mergefront(chn);
swap(chn, chnR);
} else chn.mergeback(chnR);
chnR.CH.clear();
}
if(nodXI[v.s] == idx) {
for(int qi : XQV[v.s]) {
preAns[qi] = chn.get(QE[qi]);
}
}
}
void process() {
H[0] = INF;
iota(HO+1, HO+N+1, 1);
sort(HO+1, HO+N+1, [&](int a, int b) {
if(H[a] != H[b]) return H[a] > H[b];
return a < b;
});
for(int i = 0; i <= N; i++) HRO[HO[i]] = i;
mnseg.init(HRO, N+1);
for(int i = 1; i <= Q; i++) {
C[i] = HO[mnseg.get(A[i], B[i])];
QS[i] = C[i];
QE[i] = B[i];
}
makeTree();
{ CHN chn; calTree(chn, 1); }
for(int i = 1; i <= Q; i++) {
Ans[i] = preAns[i] + ll(C[i] - A[i]) * H[C[i]];
}
reverse(H+1, H+N+1);
for(int i = 1; i <= N; i++) HO[i] = N+1 - HO[i];
for(int i = 1; i <= N; i++) HRO[HO[i]] = i;
mnseg.init(HRO, N+1);
for(int i = 1; i <= Q; i++) {
A[i] = N+1 - A[i];
B[i] = N+1 - B[i];
swap(A[i], B[i]);
C[i] = N+1 - C[i];
QS[i] = C[i];
QE[i] = B[i];
}
makeTree();
{ CHN chn; calTree(chn, 1); }
for(int i = 1; i <= Q; i++) {
ll t = preAns[i] + ll(C[i] - A[i]) * H[C[i]];
if(t < Ans[i]) Ans[i] = t;
}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
::N = sz(H);
::Q = sz(L);
for(int i = 1; i <= Q; i++) {
::A[i] = L[i-1] + 1;
::B[i] = R[i-1] + 1;
}
for(int i = 1; i <= N; i++) {
::H[i] = H[i-1];
}
process();
vector<ll> V;
for(int i = 1; i <= Q; i++) V.eb(Ans[i]);
return V;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
29148 KB |
Output is correct |
2 |
Correct |
39 ms |
29432 KB |
Output is correct |
3 |
Correct |
39 ms |
29452 KB |
Output is correct |
4 |
Correct |
38 ms |
29468 KB |
Output is correct |
5 |
Correct |
38 ms |
29404 KB |
Output is correct |
6 |
Correct |
40 ms |
29744 KB |
Output is correct |
7 |
Correct |
38 ms |
29376 KB |
Output is correct |
8 |
Correct |
39 ms |
29844 KB |
Output is correct |
9 |
Correct |
38 ms |
29652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
29148 KB |
Output is correct |
2 |
Correct |
39 ms |
29432 KB |
Output is correct |
3 |
Correct |
39 ms |
29452 KB |
Output is correct |
4 |
Correct |
38 ms |
29468 KB |
Output is correct |
5 |
Correct |
38 ms |
29404 KB |
Output is correct |
6 |
Correct |
40 ms |
29744 KB |
Output is correct |
7 |
Correct |
38 ms |
29376 KB |
Output is correct |
8 |
Correct |
39 ms |
29844 KB |
Output is correct |
9 |
Correct |
38 ms |
29652 KB |
Output is correct |
10 |
Correct |
44 ms |
30080 KB |
Output is correct |
11 |
Correct |
44 ms |
30088 KB |
Output is correct |
12 |
Correct |
43 ms |
30092 KB |
Output is correct |
13 |
Correct |
44 ms |
30084 KB |
Output is correct |
14 |
Correct |
44 ms |
30656 KB |
Output is correct |
15 |
Correct |
42 ms |
30096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
29216 KB |
Output is correct |
2 |
Correct |
79 ms |
34356 KB |
Output is correct |
3 |
Correct |
206 ms |
55152 KB |
Output is correct |
4 |
Correct |
168 ms |
45792 KB |
Output is correct |
5 |
Correct |
209 ms |
56240 KB |
Output is correct |
6 |
Correct |
204 ms |
57392 KB |
Output is correct |
7 |
Correct |
208 ms |
59904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
29216 KB |
Output is correct |
2 |
Correct |
79 ms |
34356 KB |
Output is correct |
3 |
Correct |
206 ms |
55152 KB |
Output is correct |
4 |
Correct |
168 ms |
45792 KB |
Output is correct |
5 |
Correct |
209 ms |
56240 KB |
Output is correct |
6 |
Correct |
204 ms |
57392 KB |
Output is correct |
7 |
Correct |
208 ms |
59904 KB |
Output is correct |
8 |
Correct |
179 ms |
46636 KB |
Output is correct |
9 |
Correct |
157 ms |
46416 KB |
Output is correct |
10 |
Correct |
174 ms |
46676 KB |
Output is correct |
11 |
Correct |
169 ms |
45640 KB |
Output is correct |
12 |
Correct |
160 ms |
45268 KB |
Output is correct |
13 |
Correct |
164 ms |
45808 KB |
Output is correct |
14 |
Correct |
200 ms |
55604 KB |
Output is correct |
15 |
Correct |
151 ms |
45484 KB |
Output is correct |
16 |
Correct |
205 ms |
55792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
29148 KB |
Output is correct |
2 |
Correct |
39 ms |
29432 KB |
Output is correct |
3 |
Correct |
39 ms |
29452 KB |
Output is correct |
4 |
Correct |
38 ms |
29468 KB |
Output is correct |
5 |
Correct |
38 ms |
29404 KB |
Output is correct |
6 |
Correct |
40 ms |
29744 KB |
Output is correct |
7 |
Correct |
38 ms |
29376 KB |
Output is correct |
8 |
Correct |
39 ms |
29844 KB |
Output is correct |
9 |
Correct |
38 ms |
29652 KB |
Output is correct |
10 |
Correct |
44 ms |
30080 KB |
Output is correct |
11 |
Correct |
44 ms |
30088 KB |
Output is correct |
12 |
Correct |
43 ms |
30092 KB |
Output is correct |
13 |
Correct |
44 ms |
30084 KB |
Output is correct |
14 |
Correct |
44 ms |
30656 KB |
Output is correct |
15 |
Correct |
42 ms |
30096 KB |
Output is correct |
16 |
Correct |
36 ms |
29216 KB |
Output is correct |
17 |
Correct |
79 ms |
34356 KB |
Output is correct |
18 |
Correct |
206 ms |
55152 KB |
Output is correct |
19 |
Correct |
168 ms |
45792 KB |
Output is correct |
20 |
Correct |
209 ms |
56240 KB |
Output is correct |
21 |
Correct |
204 ms |
57392 KB |
Output is correct |
22 |
Correct |
208 ms |
59904 KB |
Output is correct |
23 |
Correct |
179 ms |
46636 KB |
Output is correct |
24 |
Correct |
157 ms |
46416 KB |
Output is correct |
25 |
Correct |
174 ms |
46676 KB |
Output is correct |
26 |
Correct |
169 ms |
45640 KB |
Output is correct |
27 |
Correct |
160 ms |
45268 KB |
Output is correct |
28 |
Correct |
164 ms |
45808 KB |
Output is correct |
29 |
Correct |
200 ms |
55604 KB |
Output is correct |
30 |
Correct |
151 ms |
45484 KB |
Output is correct |
31 |
Correct |
205 ms |
55792 KB |
Output is correct |
32 |
Correct |
1271 ms |
152768 KB |
Output is correct |
33 |
Correct |
1134 ms |
149940 KB |
Output is correct |
34 |
Correct |
1275 ms |
153284 KB |
Output is correct |
35 |
Correct |
1291 ms |
152852 KB |
Output is correct |
36 |
Correct |
1121 ms |
154248 KB |
Output is correct |
37 |
Correct |
1272 ms |
153648 KB |
Output is correct |
38 |
Correct |
1769 ms |
227396 KB |
Output is correct |
39 |
Correct |
2035 ms |
227376 KB |
Output is correct |
40 |
Correct |
1318 ms |
160940 KB |
Output is correct |
41 |
Correct |
2075 ms |
291900 KB |
Output is correct |
42 |
Correct |
2273 ms |
291140 KB |
Output is correct |
43 |
Correct |
2264 ms |
291124 KB |
Output is correct |
44 |
Correct |
2091 ms |
227676 KB |
Output is correct |