#include "meetings.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
using namespace std;
ll n,i,a[101010],ST[404040],ki[101010],ka[101010],P[5050],S[5050];
void upd(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(aa==bb)ST[ee]=dd;
else
{
ll ce=(aa+bb)/2;
if(cc<=ce)upd(aa,ce,cc,dd,ee*2);
else upd(ce+1,bb,cc,dd,ee*2+1);
ST[ee]=max(ST[ee*2],ST[ee*2+1]);
}
}
ll que(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(bb<cc||dd<aa)return 0;
else
if(cc<=aa&&bb<=dd)return ST[ee];
else
{
ll ce=(aa+bb)/2;
return max(que(aa,ce,cc,dd,ee*2),que(ce+1,bb,cc,dd,ee*2+1));
}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R)
{
n=H.size();
for(i=1;i<=n;i++)a[i]=H[i-1];
for(i=1;i<=n;i++)
if(a[i]==a[i-1])
ki[i]=ki[i-1];
else
ki[i]=i;
for(i=n;i>=1;i--)
if(a[i]==a[i+1])
ka[i]=ka[i+1];
else
ka[i]=i;
for(i=1;i<=n;i++)
if(a[i]==1)
upd(1,n,i,ka[i]-ki[i]+1,1);
int Q = L.size();
std::vector<long long> C(Q);
for (int j = 0; j < Q; ++j)
{
L[j]++;
R[j]++;
if(Q<=5000&&n<=5000)
{
C[j]=1e18;
{
stack<pair<ll,ll> > st;
P[L[j]-1]=0;
for(i=L[j];i<=R[j];i++)
{
P[i]=P[i-1]+a[i];
ll las=i;
while(!st.empty()&&st.top().fi<=a[i])
{
P[i]-=(las-st.top().se)*st.top().fi;
P[i]+=(las-st.top().se)*a[i];
las=st.top().se;
st.pop();
}
st.push(mp(a[i],las));
}
}
{
stack<pair<ll,ll> > st;
S[R[j]+1]=0;
for(i=R[j];i>=L[j];i--)
{
S[i]=S[i+1]+a[i];
ll las=i;
while(!st.empty()&&st.top().fi<=a[i])
{
//cout<<"_"<<i<<"\n";
S[i]-=(st.top().se-las)*st.top().fi;
S[i]+=(st.top().se-las)*a[i];
las=st.top().se;
st.pop();
}
st.push(mp(a[i],las));
//cout<<i<<" "<<S[i]<<"\n";
}
}
for(i=L[j];i<=R[j];i++)
C[j]=min(C[j],P[i]+S[i]-a[i]);
continue;
}
//cout<<ka[L[j]]<<" "<<ki[R[j]]<<"\n";
C[j]=que(1,n,ka[L[j]]+1,ki[R[j]]-1,1);
//cout<<C[j]<<"_\n";
if(a[R[j]]==1&&ki[R[j]]>=L[j])C[j]=max(C[j],R[j]-ki[R[j]]+1);
else if(a[R[j]]==1)C[j]=max(C[j],R[j]-L[j]+1LL);
if(a[L[j]]==1&&ka[L[j]]<=R[j])C[j]=max(C[j],ka[L[j]]-L[j]+1);
else if(a[L[j]]==1)C[j]=max(C[j],R[j]-L[j]+1LL);
C[j]=2*(R[j]-L[j]+1)-C[j];
}
return C;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
476 KB |
Output is correct |
3 |
Correct |
4 ms |
504 KB |
Output is correct |
4 |
Correct |
3 ms |
504 KB |
Output is correct |
5 |
Correct |
4 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
508 KB |
Output is correct |
8 |
Correct |
1 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
476 KB |
Output is correct |
3 |
Correct |
4 ms |
504 KB |
Output is correct |
4 |
Correct |
3 ms |
504 KB |
Output is correct |
5 |
Correct |
4 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
508 KB |
Output is correct |
8 |
Correct |
1 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
504 KB |
Output is correct |
10 |
Correct |
346 ms |
732 KB |
Output is correct |
11 |
Correct |
1027 ms |
732 KB |
Output is correct |
12 |
Correct |
351 ms |
732 KB |
Output is correct |
13 |
Correct |
1045 ms |
724 KB |
Output is correct |
14 |
Correct |
260 ms |
760 KB |
Output is correct |
15 |
Correct |
264 ms |
732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
39 ms |
1932 KB |
Output is correct |
3 |
Correct |
124 ms |
7860 KB |
Output is correct |
4 |
Correct |
120 ms |
7908 KB |
Output is correct |
5 |
Correct |
95 ms |
7828 KB |
Output is correct |
6 |
Correct |
80 ms |
7176 KB |
Output is correct |
7 |
Correct |
85 ms |
6912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
39 ms |
1932 KB |
Output is correct |
3 |
Correct |
124 ms |
7860 KB |
Output is correct |
4 |
Correct |
120 ms |
7908 KB |
Output is correct |
5 |
Correct |
95 ms |
7828 KB |
Output is correct |
6 |
Correct |
80 ms |
7176 KB |
Output is correct |
7 |
Correct |
85 ms |
6912 KB |
Output is correct |
8 |
Incorrect |
117 ms |
7832 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
476 KB |
Output is correct |
3 |
Correct |
4 ms |
504 KB |
Output is correct |
4 |
Correct |
3 ms |
504 KB |
Output is correct |
5 |
Correct |
4 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
508 KB |
Output is correct |
8 |
Correct |
1 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
504 KB |
Output is correct |
10 |
Correct |
346 ms |
732 KB |
Output is correct |
11 |
Correct |
1027 ms |
732 KB |
Output is correct |
12 |
Correct |
351 ms |
732 KB |
Output is correct |
13 |
Correct |
1045 ms |
724 KB |
Output is correct |
14 |
Correct |
260 ms |
760 KB |
Output is correct |
15 |
Correct |
264 ms |
732 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
39 ms |
1932 KB |
Output is correct |
18 |
Correct |
124 ms |
7860 KB |
Output is correct |
19 |
Correct |
120 ms |
7908 KB |
Output is correct |
20 |
Correct |
95 ms |
7828 KB |
Output is correct |
21 |
Correct |
80 ms |
7176 KB |
Output is correct |
22 |
Correct |
85 ms |
6912 KB |
Output is correct |
23 |
Incorrect |
117 ms |
7832 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |