题解 | 能量辐射

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
typedef long long ll;
ll h[N],w[N];
ll ans[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i]>>w[i];
    }

    stack<pair<int,int>>stk;
    stk.push({h[1],w[1]});
    for(int i=2;i<=n;i++)
    {
        
        while(!stk.empty()&&h[i]>stk.top().first)
        {
            ans[i]+=stk.top().second;
            stk.pop();
        }
        stk.push({h[i],w[i]});
    }

    stack<pair<int,int>>stk2;
    stk2.push({h[n],w[n]});
    for(int i=n-1;i>=1;i--)
    {
        while(!stk2.empty()&&h[i]>stk2.top().first)
        {
            ans[i]+=stk2.top().second;
            stk2.pop();
        }
        stk2.push({h[i],w[i]});
    }

    // for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    // cout<<endl;

    ll res = 0;
    for(int i=1;i<=n;i++)res = max(res,ans[i]);
    cout<<res<<endl;    
    return 0;
}

单调栈秒了