#include "meetings.h"
#include <vector>
using namespace std;
#define MAX_N 5000
#define INF 1000000000000000000LL
typedef long long ll;
int N, Q;
int seg1[MAX_N*4+1];
ll seg2[MAX_N*4+1];
int two=1;
void update1(int x, int y){
x+=two; while(x>0) {seg1[x]=max(seg1[x], y); x/=2;}
}
void update2(int x, ll y){
x+=two; while(x>0){seg2[x]+=y; x/=2;}
}
int maxi(int x, int y){
x+=two; y+=two;
int ret=0;
while(x<=y){
if(x==y) return max(ret, seg1[x]);
if(x%2) ret=max(ret, seg1[x++]);
if(!(y%2))ret=max(ret, seg1[y--]);
x/=2; y/=2;
}return ret;
}
ll sum(int x, int y){
x+=two; y+=two;
ll ret=0;
while(x<=y){
if(x==y) return ret+seg2[x];
if(x%2) ret+=seg2[x++];
if(!(y%2))ret+=seg2[y--];
x/=2; y/=2;
}return ret;
}
#define MAX_N2 100001
vector<int> v;
int Li[MAX_N2+1], Ri[MAX_N2+1];
ll seg[21][MAX_N2*4+1];
void update(int h, int x, ll y){
x+=two; while(x>0) {seg[h][x]=min(seg[h][x], y); x/=2;}
}
ll min(int h, int x, int y){
x+=two; y+=two; ll ret=INF;
while(x<=y){
if(x==y) return min(ret, seg[h][x]);
if(x%2) ret=min(ret, seg[h][x++]);
if(!(y%2)) ret=min(ret, seg[h][y--]);
x/=2; y/=2;
}return ret;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
N=(int)H.size(); Q=(int)L.size();
vector<ll> C(Q);
/*
if(N<=5000 && Q<=5000){
for(int i=0; i<Q; i++) C[i]=INF;
while(two<N) two*=2;
for(int i=0; i<N; i++) update1(i, H[i]);
for(int i=0; i<N; i++){
for(int j=1; j<two*2; j++){
seg2[j]=0;
}
for(int j=0; j<N; j++){
update2(j, maxi(min(i, j), max(i, j)));
}
for(int j=0; j<Q; j++){
if(i>=L[j] && i<=R[j]) C[j]=min(C[j], sum(L[j], R[j]));
}
}
}else{//*/
while(two<N) two*=2;
for(int h=1; h<=20; h++) for(int i=1; i<two*2; i++) seg[h][i]=INF;
for(int i=0; i<N; i++){
while(!v.empty() && H[v.back()]<H[i]){
Ri[v.back()]=i; v.pop_back();
}v.push_back(i);
}while(!v.empty()) {Ri[v.back()]=N; v.pop_back();}
for(int i=N-1; i>=0; i--){
while(!v.empty() && H[v.back()]<H[i]){
Li[v.back()]=i; v.pop_back();
}v.push_back(i);
}while(!v.empty()){Li[v.back()]=-1; v.pop_back();}
int l, r;ll d=0;
for(int i=0; i<N; i++){
l=Li[i]; r=Ri[i]; d=(ll)(Ri[i]-Li[i]-1)*(ll)H[i];
for(int h=H[i]; h<=20; h++){
if(l!=-1 && H[l]==h){
d+=(ll)h*(l-Li[l]); l=Li[l];
}
if(r!=N && H[r]==h){
d+=(ll)h*(Ri[r]-r); r=Ri[r];
}
update(h, i, d+(ll)(1+l)*h+(ll)(N-r)*h);
}
}
int Hl, Hr;
vector<int> vv;
for(int i=0; i<Q; i++){
C[i]=INF;
l=L[i]; r=R[i];
while(Ri[l]<=R[i]) {vv.push_back(l);l=Ri[l];}
Hl=l;
ll RL=0;
RL = (ll)(H[Hl]-H[vv.back()])*(R[i]-Hl+1);
while(!vv.empty()){
l=vv.back(); vv.pop_back();
C[i]=min(C[i], min(H[l], l, Ri[l]-1)-(ll)L[i]*H[l]-(ll)H[l]*(N-R[i]-1)+RL);
if(!vv.empty()) RL+=(ll)(R[i]-l+1)*(H[l]-H[vv.back()]);
}
while(Li[r]>=L[i]) {vv.push_back(r);r=Li[r];}
Hr=r;
RL = (ll)(H[Hr]-H[vv.back()])*(Hr-L[i]+1);
while(!vv.empty()){
r=vv.back(); vv.pop_back();
C[i]=min(C[i], min(H[r], Li[r]+1, r)-(ll)(N-R[i]-1)*H[r]-(ll)H[r]*L[i]+RL);
if(!vv.empty()) RL += (ll) (r-L[i]+1)*(H[r]-H[vv.back()]);
}
C[i]=min(C[i], min(H[Hl], Hl, Hr)-(ll)H[Hl]*(L[i]+N-R[i]-1));
}
//}
return C;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
660 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
660 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
660 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
