codeforces 436 F Banners--ブロック
4845 ワード
ansiにpがiに等しいときの答えを表す.biのソート、cの列挙、ansiの更新.ブロック分割を考慮し,各ブロックの最大値と最大値を取得する位置を維持する.aiを更新するとans 1,ans 2⋯ansaiに1が加算されます.ブロック全体に1を加えると、明らかに最大値が変化すると、最大値を取得する位置は必ず大きくなります.では、最大値を変えるときに暴力がブロック全体を再構築すればいいのです.1つのセグメントに1を加えると、直接暴力がこのブロックを再構築します.このようなブロックはO(n)回のみ再構成され,時間複雑度はO(nn√)である.次に,最大値位置が変化するとどう判断するかを考える.現在最大値を取得している位置がiであると仮定し、kを大きくすると最大値がjとなり、fiは現在iの値を表す.得られる:fi−fjfi−fjj−i.再構成時にkの最小値を求めればよい.
コード:
コード:
#includeinline ll Max(ll x,ll y){
return xinline int Max(int x,int y){
return xinline ll Min(ll x,ll y){
return xinline void Update(int x){
for(int i=1;iif(--r[i]<=0){
r[i]=n;
for(int j=t[i]+1;b[j]==i;j++){
T=1ll*j*(f[j]+p[i]);
if(T>mx[i])mx[i]=T,t[i]=j;
}
for(int j=t[i]+1;b[j]==i;j++)
r[i]=Min(r[i],(1ll*(f[t[i]]+p[i])*t[i]-1ll*(f[j]+p[i])*j)/(j-t[i]));
}
}
for(int i=x;i&&b[i]==b[x];i--){
f[i]++;
T=1ll*i*(f[i]+p[b[x]]);
if(T>mx[b[x]])mx[b[x]]=T,t[b[x]]=i;
}
r[b[x]]=n;
for(int i=t[b[x]]+1;b[i]==b[x];i++)
r[b[x]]=Min(r[b[x]],(1ll*(f[t[b[x]]]+p[b[x]])*t[b[x]]-1ll*(f[i]+p[b[x]])*i)/(i-t[b[x]]));
}
int main(){
scanf("%d%d",&n,&w);
for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y),M=Max(a[i].x,M);
for(S=sqrt(M),i=1;i<=M;i++)b[i]=i/S+1;
for(i=1;i<=b[M];i++)t[i]=(i-1)*S;
sort(a+1,a+n+1,Cmp);
for(i=0;i<=a[n].y+1;i++){
for(;j1].yfor(k=1,Ans=x=0;k<=b[M];k++)if(mx[k]>Ans)Ans=mx[k],x=t[k];
printf("%I64d %d
",Ans+1ll*i*w*(n-j),x);
}
return 0;
}