제출 #614142

#제출 시각아이디문제언어결과실행 시간메모리
614142chirathnirodha모임들 (IOI18_meetings)C++17
19 / 100
511 ms4144 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...