#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 750005;
const int MAXT = 2100000;
const int inf = 1e9 + 10;
struct seg{
int lim;
pi tree[MAXT];
void init(vector<int> &v){
for(lim = 1; lim <= v.size(); lim <<= 1);
fill(tree, tree + MAXT, pi(-inf, 0));
for(int i=0; i<v.size(); i++) tree[i + lim] = pi(v[i], i);
for(int i=lim-1; i; i--) tree[i] = max(tree[2*i], tree[2*i+1]);
}
pi query(int s, int e){
s += lim;
e += lim;
pi ret(-inf, 0);
while(s < e){
if(s%2 == 1) ret = max(ret, tree[s++]);
if(e%2 == 0) ret = max(ret, tree[e--]);
s >>= 1;
e >>= 1;
}
if(s == e) ret = max(ret, tree[s]);
return ret;
}
}seg;
struct node{
int s, e, rep; // node range
int lp, rp; // pointers
int h; // height
}tr[MAXN];
int ptr, loc[MAXN], parL[MAXN], parR[MAXN];
lint dp[MAXN], lgo[MAXN], rgo[MAXN];
lint L_intercept[MAXN], R_intercept[MAXN];
void make_tree(int s, int e, int v){
int h, m;
tie(h, m) = seg.query(s, e);
loc[m] = v;
tr[v] = {s, e, m, -1, -1, h};
if(s <= m - 1){
ptr++;
tr[v].lp = ptr;
make_tree(s, m-1, tr[v].lp);
}
if(m + 1 <= e){
ptr++;
tr[v].rp = ptr;
make_tree(m+1, e, tr[v].rp);
}
}
struct tree_cht{
struct queries{
int s, e, x, idx;
};
int n, par[MAXN];
int a[MAXN]; lint b[MAXN];
vector<int> gph[MAXN];
vector<queries> query;
int sz[MAXN], dfn[MAXN], chn[MAXN], cnt[MAXN], piv;
void dfs(int x){
sz[x] = 1;
for(auto &i : gph[x]){
dfs(i);
sz[x] += sz[i];
}
}
void hld(int x){
dfn[x] = ++piv;
cnt[chn[x]]++;
if(gph[x].empty()) return;
chn[gph[x][0]] = chn[x];
hld(gph[x][0]);
for(int i=1; i<gph[x].size(); i++){
chn[gph[x][i]] = gph[x][i];
hld(gph[x][i]);
}
}
void build(int _n, int *p, node *t, lint *intercept){
a[0] = inf;
n = _n + 1;
for(int i=1; i<n; i++){
par[i] = p[i-1] + 1;
gph[par[i]].push_back(i);
}
dfs(0);
for(int i=0; i<n; i++){
sort(gph[i].begin(), gph[i].end(), [&](const int &a, const int &b){
return sz[a] > sz[b];
});
}
hld(0);
for(int i=1; i<n; i++){
a[dfn[i]] = t[i-1].h;
b[dfn[i]] = intercept[i-1];
}
}
void add_query(int s, int e, int x){
query.push_back({s + 1, e + 1, x, (int)query.size()});
}
struct range_query{
int l, r, x, idx;
};
vector<pi> prefix_query[MAXN];
vector<range_query> rquery;
vector<lint> batch(){
vector<lint> ret(query.size(), 1e18);
for(int i=0; i<query.size(); i++){
int pos = query[i].s;
while(chn[pos] != chn[query[i].e]){
prefix_query[dfn[pos]].push_back(pi(query[i].x, query[i].idx));
pos = par[chn[pos]];
}
if(dfn[query[i].e] < dfn[pos]){
rquery.push_back({dfn[query[i].e] + 1, dfn[pos], query[i].x, query[i].idx});
}
}
for(int i=0; i<n; i++){
if(chn[i] == i){
for(int j=dfn[i]; j<dfn[i]+cnt[i]; j++){
for(auto &k : prefix_query[j]){
for(int l=dfn[i]; l<=j; l++){
ret[k.second] = min(ret[k.second], 1ll * a[l] * k.first + b[l]);
}
}
}
}
}
for(auto &i : rquery){
for(int j=i.l; j<=i.r; j++){
ret[i.idx] = min(ret[i.idx], 1ll * a[j] * i.x + b[j]);
}
}
return ret;
}
}t1, t2;
vector<lint> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
int n = H.size();
int q = L.size();
seg.init(H);
make_tree(0, n-1, 0);
for(int i=ptr; i>=0; i--){
dp[i] = 1ll * H[tr[i].rep] * (tr[i].e - tr[i].s + 1);
if(~tr[i].lp){
dp[i] = min(dp[i], dp[tr[i].lp] + 1ll * H[tr[i].rep] * (tr[i].e - tr[i].rep + 1));
}
if(~tr[i].rp){
dp[i] = min(dp[i], dp[tr[i].rp] + 1ll * H[tr[i].rep] * (tr[i].rep - tr[i].s + 1));
}
}
for(int i=0; i<=ptr; i++){
if(tr[i].s - 1 >= 0) parR[i] = loc[tr[i].s - 1];
else parR[i] = -1;
if(tr[i].e + 1 < n) parL[i] = loc[tr[i].e + 1];
else parL[i] = -1;
if(~tr[i].lp){
lgo[tr[i].lp] = lgo[i] + 1ll * H[tr[i].rep] * (tr[i].e - tr[i].rep + 1);
rgo[tr[i].lp] = rgo[i];
}
if(~tr[i].rp){
lgo[tr[i].rp] = lgo[i];
rgo[tr[i].rp] = rgo[i] + 1ll * H[tr[i].rep] * (tr[i].rep - tr[i].s + 1);
}
L_intercept[i] = lgo[i] + 1ll * tr[i].h * (tr[i].e + 1);
if(~tr[i].rp){
L_intercept[i] = min(L_intercept[i], lgo[i] + 1ll * tr[i].h * (tr[i].rep + 1) + dp[tr[i].rp]);
}
R_intercept[i] = rgo[i] + 1ll * tr[i].h * (1 - tr[i].s);
if(~tr[i].lp){
R_intercept[i] = min(R_intercept[i], rgo[i] + 1ll * tr[i].h * (1 - tr[i].rep) + dp[tr[i].lp]);
}
}
t1.build(ptr + 1, parL, tr, L_intercept);
t2.build(ptr + 1, parR, tr, R_intercept);
vector<pi> lca(q);
for(int i=0; i<q; i++){
lca[i] = seg.query(L[i], R[i]);
t1.add_query(loc[L[i]], loc[lca[i].second], -L[i]);
t2.add_query(loc[R[i]], loc[lca[i].second], R[i]);
}
auto sol1 = t1.batch();
auto sol2 = t2.batch();
vector<lint> ret(q);
for(int i=0; i<q; i++){
pi p = lca[i];
int root_num = loc[p.second];
ret[i] = 1ll * (R[i] - L[i] + 1) * p.first;
if(L[i] < p.second){
ret[i] = min(ret[i], sol1[i] + 1ll * (R[i] - p.second + 1) * p.first - lgo[tr[root_num].lp]);
}
if(p.second < R[i]){
ret[i] = min(ret[i], sol2[i] + 1ll * (p.second - L[i] + 1) * p.first - rgo[tr[root_num].rp]);
}
}
return ret;
}
Compilation message
meetings.cpp: In member function 'void seg::init(std::vector<int>&)':
meetings.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(lim = 1; lim <= v.size(); lim <<= 1);
~~~~^~~~~~~~~~~
meetings.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++) tree[i + lim] = pi(v[i], i);
~^~~~~~~~~
meetings.cpp: In member function 'void tree_cht::hld(int)':
meetings.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<gph[x].size(); i++){
~^~~~~~~~~~~~~~
meetings.cpp: In member function 'std::vector<long long int> tree_cht::batch()':
meetings.cpp:117:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<query.size(); i++){
~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
87416 KB |
Output is correct |
2 |
Correct |
86 ms |
87972 KB |
Output is correct |
3 |
Correct |
85 ms |
87900 KB |
Output is correct |
4 |
Correct |
87 ms |
87980 KB |
Output is correct |
5 |
Correct |
85 ms |
87932 KB |
Output is correct |
6 |
Correct |
86 ms |
88092 KB |
Output is correct |
7 |
Correct |
88 ms |
87904 KB |
Output is correct |
8 |
Correct |
85 ms |
88112 KB |
Output is correct |
9 |
Correct |
85 ms |
88060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
87416 KB |
Output is correct |
2 |
Correct |
86 ms |
87972 KB |
Output is correct |
3 |
Correct |
85 ms |
87900 KB |
Output is correct |
4 |
Correct |
87 ms |
87980 KB |
Output is correct |
5 |
Correct |
85 ms |
87932 KB |
Output is correct |
6 |
Correct |
86 ms |
88092 KB |
Output is correct |
7 |
Correct |
88 ms |
87904 KB |
Output is correct |
8 |
Correct |
85 ms |
88112 KB |
Output is correct |
9 |
Correct |
85 ms |
88060 KB |
Output is correct |
10 |
Correct |
92 ms |
89208 KB |
Output is correct |
11 |
Correct |
92 ms |
89144 KB |
Output is correct |
12 |
Correct |
93 ms |
89256 KB |
Output is correct |
13 |
Correct |
92 ms |
89168 KB |
Output is correct |
14 |
Correct |
94 ms |
89216 KB |
Output is correct |
15 |
Correct |
91 ms |
89228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
87348 KB |
Output is correct |
2 |
Correct |
205 ms |
94556 KB |
Output is correct |
3 |
Correct |
2233 ms |
120704 KB |
Output is correct |
4 |
Correct |
318 ms |
118960 KB |
Output is correct |
5 |
Correct |
207 ms |
117112 KB |
Output is correct |
6 |
Correct |
283 ms |
120220 KB |
Output is correct |
7 |
Correct |
2774 ms |
121868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
87348 KB |
Output is correct |
2 |
Correct |
205 ms |
94556 KB |
Output is correct |
3 |
Correct |
2233 ms |
120704 KB |
Output is correct |
4 |
Correct |
318 ms |
118960 KB |
Output is correct |
5 |
Correct |
207 ms |
117112 KB |
Output is correct |
6 |
Correct |
283 ms |
120220 KB |
Output is correct |
7 |
Correct |
2774 ms |
121868 KB |
Output is correct |
8 |
Correct |
487 ms |
120144 KB |
Output is correct |
9 |
Correct |
834 ms |
118752 KB |
Output is correct |
10 |
Correct |
285 ms |
121792 KB |
Output is correct |
11 |
Correct |
331 ms |
121288 KB |
Output is correct |
12 |
Correct |
263 ms |
118900 KB |
Output is correct |
13 |
Correct |
321 ms |
121844 KB |
Output is correct |
14 |
Correct |
2224 ms |
120552 KB |
Output is correct |
15 |
Correct |
320 ms |
123764 KB |
Output is correct |
16 |
Correct |
1416 ms |
121708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
87416 KB |
Output is correct |
2 |
Correct |
86 ms |
87972 KB |
Output is correct |
3 |
Correct |
85 ms |
87900 KB |
Output is correct |
4 |
Correct |
87 ms |
87980 KB |
Output is correct |
5 |
Correct |
85 ms |
87932 KB |
Output is correct |
6 |
Correct |
86 ms |
88092 KB |
Output is correct |
7 |
Correct |
88 ms |
87904 KB |
Output is correct |
8 |
Correct |
85 ms |
88112 KB |
Output is correct |
9 |
Correct |
85 ms |
88060 KB |
Output is correct |
10 |
Correct |
92 ms |
89208 KB |
Output is correct |
11 |
Correct |
92 ms |
89144 KB |
Output is correct |
12 |
Correct |
93 ms |
89256 KB |
Output is correct |
13 |
Correct |
92 ms |
89168 KB |
Output is correct |
14 |
Correct |
94 ms |
89216 KB |
Output is correct |
15 |
Correct |
91 ms |
89228 KB |
Output is correct |
16 |
Correct |
83 ms |
87348 KB |
Output is correct |
17 |
Correct |
205 ms |
94556 KB |
Output is correct |
18 |
Correct |
2233 ms |
120704 KB |
Output is correct |
19 |
Correct |
318 ms |
118960 KB |
Output is correct |
20 |
Correct |
207 ms |
117112 KB |
Output is correct |
21 |
Correct |
283 ms |
120220 KB |
Output is correct |
22 |
Correct |
2774 ms |
121868 KB |
Output is correct |
23 |
Correct |
487 ms |
120144 KB |
Output is correct |
24 |
Correct |
834 ms |
118752 KB |
Output is correct |
25 |
Correct |
285 ms |
121792 KB |
Output is correct |
26 |
Correct |
331 ms |
121288 KB |
Output is correct |
27 |
Correct |
263 ms |
118900 KB |
Output is correct |
28 |
Correct |
321 ms |
121844 KB |
Output is correct |
29 |
Correct |
2224 ms |
120552 KB |
Output is correct |
30 |
Correct |
320 ms |
123764 KB |
Output is correct |
31 |
Correct |
1416 ms |
121708 KB |
Output is correct |
32 |
Correct |
3297 ms |
379908 KB |
Output is correct |
33 |
Correct |
1488 ms |
364676 KB |
Output is correct |
34 |
Correct |
3053 ms |
354892 KB |
Output is correct |
35 |
Correct |
3357 ms |
351916 KB |
Output is correct |
36 |
Correct |
2776 ms |
331252 KB |
Output is correct |
37 |
Correct |
3333 ms |
355360 KB |
Output is correct |
38 |
Execution timed out |
5596 ms |
325420 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |