이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push
typedef long long ll;
int n,q;
vector<ll> hei;
vector<ll> SUB_1_2(vector<int> L,vector<int> R) {
vector<ll> C;
for(int h=0;h<q;h++){
ll ans=INT64_MAX;
ll vall[n],valr[n];
vector<int> v;
ll cur=hei[L[h]];vall[L[h]]=cur;
v.PB(L[h]);
for(int i=L[h]+1;i<=R[h];i++){
while(!v.empty()){
int last=v.back();
if(hei[last]>=hei[i])break;
v.pop_back();
if(v.empty())cur+=(hei[i]-hei[last])*(last-L[h]+1);
else cur+=(hei[i]-hei[last])*(last-v.back());
}
v.PB(i);cur+=hei[i];
vall[i]=cur;
}
v.clear();
cur=hei[R[h]];valr[R[h]]=cur;
v.PB(R[h]);
for(int i=R[h]-1;i>=L[h];i--){
while(!v.empty()){
int last=v.back();
if(hei[last]>=hei[i])break;
v.pop_back();
if(v.empty())cur+=(hei[i]-hei[last])*(R[h]-last+1);
else cur+=(hei[i]-hei[last])*(v.back()-last);
}
v.PB(i);cur+=hei[i];
valr[i]=cur;
}
for(int i=L[h];i<=R[h];i++){
ans=min(ans,vall[i]+valr[i]-hei[i]);
}
C.PB(ans);
}
return C;
}
int lf[100000],ri[100000];
int seg[400010];
void update(int a,int b,int c,int x,int y){
seg[c]=max(seg[c],y-x+1);
if(a==b)return;
int m=(a+b)/2;
if(y<=m)update(a,m,2*c,x,y);
else if(x>m)update(m+1,b,2*c+1,x,y);
}
int findseg(int a,int b,int c,int x,int y,int w,int z){
if(a==x && b==y)return seg[c];
int m=(a+b)/2;
if(y<=m)return findseg(a,m,2*c,x,y,w,z);
else if(x>m)return findseg(m+1,b,2*c+1,x,y,w,z);
int comb=lf[m]+ri[m]-1;
comb=min(comb,z-w+1);
return max(comb,max(findseg(a,m,2*c,x,m,w,z),findseg(m+1,b,2*c+1,m+1,y,w,z)));
}
vector<ll> SUB_3(vector<int> L,vector<int> R) {
memset(seg,0,sizeof(seg));
int cur=-1;
for(int i=0;i<n;i++){
lf[i]=cur+1;
if(hei[i]==2){
if(cur+1<=i-1)update(0,n-1,1,cur+1,i-1);
cur=i;
lf[i]=0;
}
}
if(cur+1<=n-1)update(0,n-1,1,cur+1,n-1);
cur=n;
for(int i=n-1;i>=0;i--){
ri[i]=cur-1;
if(hei[i]==2){
ri[i]=0;
cur=i;
}
}
vector<ll> C;
for(int i=0;i<q;i++){
int all=R[i]-L[i]+1;
int ones=findseg(0,n-1,1,L[i],R[i],L[i],R[i]);
int lo=min(lf[R[i]],all);
int ro=min(ri[L[i]],all);
ones=max(ones,max(lo,ro));
ll val=ones+2*(all-ones);
C.PB(val);
}
return C;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
n=H.size();q=L.size();
for(int i=0;i<n;i++)hei.PB((ll)H[i]);
if(n<=5000 && q<=5000)return SUB_1_2(L,R);
else return SUB_3(L,R);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |