#include "meetings.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=750005;
const int mxM=2200005;
const int mxK=61;
const int MOD=1e9+7;
const ll INF=1e18;
int N, Q;
ll H[mxN];
pii qry[mxN];
ll l[mxN], r[mxN];
int spsl[mxN][20], spsr[mxN][20];
ll ldp[mxN], rdp[mxN]; // ldp[i] : [l[i]+1, i]에서 시작점을 선택해서 [l[i]+1, i-1]에 대한 최소 비용
ll rval[mxN], lval[mxN];
ll ans[mxN];
void init(vector <int> h, vector <int> L, vector <int> R){
N=h.size();
for(int i=0;i<N;i++) H[i]=h[i];
Q = L.size();
for(int i=0;i<Q;i++) qry[i]=pii(L[i], R[i]);
}
void input(){
cin >> N >> Q;
for(int i=0;i<N;i++) cin >> H[i];
for(int i=0;i<Q;i++) cin >> qry[i].fi >> qry[i].se;
}
void make_cartesian_tree(){ // 두 산의 높이가 같으면 오른쪽에 있는 산의 높이가 더 높다
stack <int> stk;
for(int i=0;i<N;i++){
while(stk.size() && H[stk.top()]<=H[i]) stk.pop();
if(stk.size()) l[i]=stk.top();
else l[i]=-1;
stk.push(i);
}
while(stk.size()) stk.pop();
for(int i=N-1;i>=0;i--){
while(stk.size() && H[stk.top()]<H[i]) stk.pop();
if(stk.size()) r[i]=stk.top();
else r[i]=-1;
stk.push(i);
}
}
void make_dp(){
//길이 2짜리 segment의 비용은 0이다
vector <pii> v;
for(int i=0;i<N;i++){
if(l[i]!=-1 && r[i]!=-1) v.emplace_back(max(i-l[i], r[i]-i), i);
}
sort(all(v));
for(auto [d, i] : v){
if(H[l[i]]<=H[r[i]]){
int now=l[i];
rdp[now]=max(rdp[i]+(i-l[i])*H[i], ldp[i]+(r[i]-i)*H[i]);
}
else{
int now=r[i];
ldp[now]=max(rdp[i]+(i-l[i])*H[i], ldp[i]+(r[i]-i)*H[i]);
}
}
}
void make_lrval(){
for(int i=N-1;i>=0;i--){
if(r[i]==-1) rval[i]=(N-i)*H[i];
else rval[i]=(r[i]-i)*H[i]+rval[r[i]];
}
for(int i=0;i<N;i++){
if(l[i]==-1) lval[i]=(i+1)*H[i];
else lval[i]=(i-l[i])*H[i]+lval[l[i]];
}
}
void solv_query(){
for(int i=0;i<Q;i++) ans[i]=INF;
for(int i=0;i<Q;i++){
auto [s, e]=qry[i];
int now=s;
int hmax=now;
while(r[hmax]!=-1 && r[hmax]<=e) hmax=r[hmax];
while(r[now]!=-1 && r[now]<=e){
ans[i]=min(ans[i], rdp[now]+(now-s+1)*H[now]+rval[r[now]]-rval[hmax]+(e-hmax+1)*H[hmax]);
now=r[now];
}
ans[i]=min(ans[i], H[now]*(e-s+1));
now=e;
while(l[now]!=-1 && l[now]>=s){
ans[i]=min(ans[i], ldp[now]+(e-now+1)*H[now]+lval[l[now]]-lval[hmax]+(hmax-s+1)*H[hmax]);
now=l[now];
}
}
//for(int i=0;i<Q;i++) cout << ans[i] << '\n';
}
void solv(){
make_cartesian_tree();
make_dp();
//for(int i=0;i<N;i++) printf("l[%d]=%d, r[%d]=%d\n", i, l[i], i, r[i]);
make_lrval();
//for(int i=0;i<N;i++) printf("l/rval[%d]=%lld %lld\n", i, lval[i], rval[i]);
solv_query();
}
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
init(h, L, R);
solv();
vector <ll> C(Q);
for(int j=0;j<Q;j++) C[j]=ans[j];
return C;
}
/*
int main()
{
gibon
input();
solv();
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
281 ms |
2992 KB |
Output is correct |
| 3 |
Execution timed out |
5534 ms |
12344 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
281 ms |
2992 KB |
Output is correct |
| 3 |
Execution timed out |
5534 ms |
12344 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
