提交记录

为什么我把 $a_{i-1} \le a_i \ge a_{i+1}$ 的 $a_i$ 变成 $a_{i-1}+a_{i+1}-a_i$ 就 WA，而按照题解做法把 $a_{i-2} \le a_{i-1} \ge a_i$ 的 $a_i$ 变成 $a_{i-2} + a_i - a_{i-1}$ 就 AC ?

/*
 * @Author: Michael Lee
 * @Date: 2022-11-13 18:00:36
 * @LastEditors: Michael Lee
 * @LastEditTime: 2022-11-13 18:29:42
 * @Description: 
 */
#define fastIO
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

/***********fast IO***********/
#ifdef fastIO
char buf[1<<21],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename T> inline void read(T &x)
{
    char ch;bool flag = 0;
    while(!isdigit(ch=getchar()))
        (ch=='-')&&(flag=true);
    for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
    (flag)&&(x=-x);
}
template<typename T, typename...L> inline void read(T &x, L &...l) { read(x), read(l...); }
template<typename T> inline void print(T x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
#endif
/***********fast IO***********/

typedef long long ll;
const int N=1e6+10;
int n,m;
ll v[N],sum,s,val;
int l[N],r[N],tot;
bool tag[N];
int main()
{
    #ifndef ONLINE_JUDGE
    // freopen("P3210.in","r",stdin);
    // freopen("P3210.out","w",stdout);
    #endif
    read(n);
    r[0]=1,l[n+1]=n;
    for(int i=1;i<=n;i++)
        read(v[i]),sum+=v[i],l[i]=i-1,r[i]=i+1,tag[i]=!!v[i];
    // for(int i=3;i!=n+1;i=r[i])
    //     while(tag[i]&&tag[l[i]]&&tag[l[l[i]]]&&v[i]<=v[l[i]]&&v[l[i]]>=v[l[l[i]]])
    //         v[i]=v[i]+v[l[l[i]]]-v[l[i]],r[l[l[l[i]]]]=i,l[i]=l[l[l[i]]];
    for(int i=2;i<n;i=r[i])
        while(tag[i]&&tag[l[i]]&&tag[r[i]]&&v[i]>=v[l[i]]&&v[i]>=v[r[i]])
            v[i]=v[l[i]]+v[r[i]]-v[i],r[l[l[i]]]=l[r[r[i]]]=i,l[i]=l[l[i]],r[i]=r[r[i]];
    int L=r[0],R=l[n+1];
    while(v[L]>=v[r[L]]&&tag[L]&&tag[r[L]]) s+=v[r[L]]-v[L],L=r[r[L]];
    while(v[R]>=v[l[R]]&&tag[R]&&tag[l[R]]) s+=v[l[R]]-v[R],R=l[l[R]];
    for(int i=L;i<=R;i=r[i])
        if(tag[i])
            v[++tot]=v[i];
    sort(v+1,v+1+tot,[](ll a,ll b){return a>b;}); v[++tot]=s;
    for(int i=1;i<=tot;i++)
        if(i&1) val+=v[i];
        else    val-=v[i];
    cout<<(sum+val)/2<<' '<<(sum-val)/2<<endl;

    #ifdef fastIO
    fwrite(obuf,p3-obuf,1,stdout);
    #endif
    return 0;
}