ALAKE - Hồ nhân tạo
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 100100
typedef long long ll;
int w[MAX];
int sw[MAX];
int h[MAX];
ll ans[MAX];
int rmq[MAX][20];
ll cur;
int lg2[MAX];
int n,sta;
int hmin(const int &x,const int &y) {
if (h[x]<h[y]) return (x); else return (y);
}
int hmax(const int &x,const int &y) {
if (h[x]>h[y]) return (x); else return (y);
}
void init(void) {
scanf("%d",&n);
int i;
sta=1;
for (i=1;i<=n;i=i+1) {
scanf("%d",&w[i]);
scanf("%d",&h[i]);
sw[i]=sw[i-1]+w[i];
sta=hmin(sta,i);
}
cur=0LL;
}
void setup_rmq(void) {
int i,j;
for (i=1;i<=n;i=i+1) rmq[i][0]=i;
for (i=1;(1<<i)<=n;i=i+1)
for (j=1;j+(1<<i)-1<=n;j=j+1)
rmq[j][i]=hmax(rmq[j][i-1],rmq[j+(1<<(i-1))][i-1]);
for (i=1;i<=n;i=i+1) {
while ((1<<lg2[i])<=i) lg2[i]++;
lg2[i]--;
}
}
int get_max(const int &i,const int &j) {
int k=lg2[j-i+1];
return (hmax(rmq[i][k],rmq[j-(1<<k)+1][k]));
}
void fill(const int &l,const int &r) {
if (l>r) return;
if (l==r) {
cur+=w[l];
ans[l]=cur;
return;
}
int m=get_max(l,r);
if (l<=sta && sta<=r) {
if (sta<m) {
fill(l,m-1);
cur+=1LL*(h[m]-h[get_max(l,m-1)]-1)*(sw[m-1]-sw[l-1]);
fill(m+1,r);
cur+=1LL*(h[m]-h[get_max(m+1,r)]-1)*(sw[r]-sw[m]);
cur+=1LL*(sw[r]-sw[l-1]);
ans[m]=cur;
}
else {
fill(m+1,r);
cur+=1LL*(h[m]-h[get_max(m+1,r)]-1)*(sw[r]-sw[m]);
fill(l,m-1);
cur+=1LL*(h[m]-h[get_max(l,m-1)]-1)*(sw[m-1]-sw[l-1]);
cur+=sw[r]-sw[l-1];
ans[m]=cur;
}
}
if (sta<l) {
fill(l,m-1);
cur+=1LL*(h[m]-h[get_max(l,m-1)]-1)*(sw[m-1]-sw[l-1]);
fill(m+1,r);
cur+=1LL*(h[m]-h[get_max(m+1,r)]-1)*(sw[r]-sw[m]);
cur+=1LL*(sw[r]-sw[l-1]);
ans[m]=cur;
}
if (sta>r) {
fill(m+1,r);
cur+=1LL*(h[m]-h[get_max(m+1,r)]-1)*(sw[r]-sw[m]);
fill(l,m-1);
cur+=1LL*(h[m]-h[get_max(l,m-1)]-1)*(sw[m-1]-sw[l-1]);
cur+=sw[r]-sw[l-1];
ans[m]=cur;
}
}
void process(void) {
fill(1,n);
int i;
for (i=1;i<=n;i=i+1) printf("%lld\n",ans[i]);
}
int main(void) {
init();
setup_rmq();
process();
return 0;
}