Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const maxn=100010;
var n,x,min:longint;
    re:qword;
    l,r:array[0..maxn] of longint;
    w,h,a:array[0..maxn] of qword;

procedure rf;
var i:longint;
begin
     readln(n);
     min:=maxlongint;
     for i:=1 to n do
     begin
          readln(w[i],h[i]);
          if h[i]<min then
          begin
               min:=h[i];
               x:=i;
          end;
          l[i]:=i-1; r[i]:=i+1;
     end;
     h[0]:=maxlongint; h[n+1]:=maxlongint;
end;

procedure pr;
var i,t:longint;
begin
     re:=0;
     repeat
           if h[l[x]]<h[r[x]] then
           begin
                if h[l[x]]<h[x] then
                begin
                     x:=l[x];
                     a[x]:=re+w[x];
                end
                else
                begin
                     a[x]:=re+w[x];
                     re:=re+w[x]*(h[l[x]]-h[x]);
                     inc(w[l[x]],w[x]);
                     r[l[x]]:=r[x]; l[r[x]]:=l[x]; x:=l[x];
                     a[x]:=re+w[x];
                end;
           end
           else
           begin
                if h[r[x]]<h[x] then
                begin
                     x:=r[x];
                     a[x]:=re+w[x];
                end
                else
                begin
                     a[x]:=re+w[x];
                     re:=re+w[x]*(h[r[x]]-h[x]);
                     inc(w[r[x]],w[x]);
                     l[r[x]]:=l[x]; r[l[x]]:=r[x]; x:=r[x];
                end;
           end;
           if (x=0) or (x=n+1) then exit;
     until false;
end;

procedure wf;
var i:longint;
begin
     for i:=1 to n do writeln(a[i]);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 1e5 + 2, INF = 1e9 + 7;
int h[N], w[N], next[N], prev[N], n;
long long res[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    h[0] = h[n + 1] = INF;
    for(int i = 1; i <= n; ++i) cin >> w[i] >> h[i];
    for(int i = 0; i <= n + 1; ++i) prev[i] = i - 1, next[i] = i + 1;
    int index = min_element(h + 1, h + n + 1) - h;
    long long total = 0;
    while(h[index] < INF) {
        res[index] = total + w[index];
        next[prev[index]] = next[index];
        prev[next[index]] = prev[index];
        if(h[next[index]] < h[prev[index]]) {
            w[next[index]] += w[index];
            total += 1LL * (h[next[index]] - h[index]) * w[index];
            index = next[index];
            while(h[next[index]] < h[index]) index = next[index];
        } else {
            w[prev[index]] += w[index];
            total += 1LL * (h[prev[index]] - h[index]) * w[index];
            index = prev[index];
            while(h[prev[index]] < h[index]) index = prev[index];
        }
    }
    for(int i = 1; i <= n; ++i)
        printf("%lld\n", res[i]);
    return 0;
}

Code mẫu của RR

//Written by RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       100111;

var
  f1,f2         :       text;
  n,li          :       longint;
  h,left,right,
  stack,w,sumw  :       array[0..MAXN] of longint;

  timel,neighl,neighr,sum,
  timer,time    :       array[0..MAXN] of int64;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
    begin
      read(f1,n); li:=1;
      for i:=1 to n do
        begin
          read(f1,w[i],h[i]);
          sum[i]:=sum[i-1]+int64(h[i])*w[i];
          sumw[i]:=sumw[i-1]+w[i];
          if h[i]<h[li] then
            li:=i;
        end;
    end;

procedure init;
    var
      i,top:longint;
    begin
      h[0]:=1000111000; h[n+1]:=h[0];
      top:=0; stack[top]:=0;
      for i:=1 to n do
        begin
          while (top>0) and (h[stack[top]]<=h[i]) do dec(top);
          left[i]:=stack[top];
          inc(top); stack[top]:=i;
        end;
      top:=0; stack[top]:=n+1;
      for i:=n downto 1 do
        begin
          while (top>0) and (h[stack[top]]<=h[i]) do dec(top);
          right[i]:=stack[top];
          inc(top); stack[top]:=i;
        end;

      for i:=1 to n do
        begin
          neighl[i]:=int64(h[i])*(sumw[i]-sumw[left[i]]) -(sum[i]-sum[left[i]]);
          neighr[i]:=int64(h[i])*(sumw[right[i]-1]-sumw[i])-(sum[right[i]-1]-sum[i]);
        end;
    end;

procedure solve;
    var
      i,u:longint;
    begin
      time[li]:=w[li];
      for i:=li+1 to n do
        begin
          u:=left[i];
          timel[i]:=timel[u]+neighl[i];
          time [i]:=timel[i]+neighr[i]+sumw[right[i]-1]-sumw[left[i]];
        end;

      for i:=li-1 downto 1 do
        begin
          u:=right[i];
          timer[i]:=timer[u]+neighr[i];
          time [i]:=timer[i]+neighl[i]+sumw[right[i]-1]-sumw[left[i]];
        end;
      for i:=1 to n do
        writeln(f2,time[i]);
    end;

begin
  openF;
  inp;
  init;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
//#include <conio.h>

#define maxn 100003
#define oo 1000000001

long long n,w[maxn],h[maxn],t[maxn],s[maxn],kq[maxn],mini,tong=0;

int main()
{
    //freopen("ALAKE.in","r",stdin);

    scanf("%lld",&n);

    h[0] = oo;
    h[n+1] = oo;
    mini = 1;

    for(int i = 1;i<=n;i++)
    {
        scanf("%lld %lld",&w[i],&h[i]);
        t[i] = i-1;
        s[i] = i+1;
        if(h[i]<h[mini])
             mini = i;
    }

    while(h[mini]<oo)
    {
        kq[mini] = tong+w[mini];
        s[t[mini]] = s[mini];
        t[s[mini]] = t[mini];

        if(h[t[mini]]<h[s[mini]])
        {
            tong = tong + w[mini]*(h[t[mini]]-h[mini]);
            w[t[mini]] += w[mini];
            mini = t[mini];
            while(mini!= 0 && h[t[mini]]<h[mini])
                mini = t[mini];
        }

        else
        {
            tong = tong + w[mini]*(h[s[mini]]-h[mini]);
            w[s[mini]] += w[mini];
            mini = s[mini];
            while(mini!=n+1 && h[s[mini]]<h[mini])
                mini = s[mini];
        }
    }

    for(int i = 1;i<=n;i++)
        printf("%lld\n",kq[i]);

    //getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int w[100010],h[100010],n;
int L[100010],R[100010];
long long ret[100010];

int main()
{
//    freopen("alake.5.in","r",stdin);
//    freopen("alake.out","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d %d", &w[i], &h[i]);
    h[0] = h[n + 1] = 1 << 30;

    int j = 1;
    L[1] = 0;
    for (int i = 2; i <= n; i++) if (h[i] > h[i - 1]) L[i] = j; else
    {
        L[i] = i - 1;  j = i;
    }
    j = n;
    R[n] = n + 1;
    for (int i = n - 1; i; i--) if (h[i] > h[i + 1]) R[i] = j; else
    {
        R[i] = i + 1;  j = i;
    }

    int pos = 1;
    long long T = 0;
    for (int i = 2; i <= n; i++) if (h[i] < h[pos]) pos = i;
    int cnt = n;
    while (cnt > 1)
    {
      cnt--;
      if (h[pos] > h[L[pos]]) pos = L[pos];
      else if (h[pos] > h[R[pos]]) pos = R[pos];
      ret[pos] = T + w[pos];

      if (h[L[pos]] > h[R[pos]])
      {
        T += 1LL * (h[R[pos]] - h[pos]) * w[pos];
        w[R[pos]] += w[pos];
        L[R[pos]] = L[pos];
        pos = R[pos];
      }
      else
      {
          T += 1LL * (h[L[pos]] - h[pos]) * w[pos];
          w[L[pos]] += w[pos];
          R[L[pos]] = R[pos];
          pos = L[pos];
      }
    }
    ret[pos] = T + w[pos];

//    for (int i = 1; i <= n; i++) cout << ret[i] << endl;
    for (int i = 1; i <= n; i++) printf("%lld\n", ret[i]);
}

Code mẫu của skyvn97

#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;
}