李超WA80pts on #5,#10,#16~#17,#19求调

toolong114514 @ 2024-05-27 22:22:30

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
#define int long long
const int INF=1e18;
const double eps=1e-10;
const int N=1e6+10;
struct node{
    int l,r,bst;
}tree[4*N];
struct ccf{
    int k,b;
}ln[N];
void build(int pos,int lft,int rgt){
    tree[pos].l=lft;
    tree[pos].r=rgt;
    if(lft==rgt) return;
    int mid=(lft+rgt)/2;
    build(pos*2,lft,mid);
    build(pos*2+1,mid+1,rgt);
}
void upd(int pos,int num){
    int mid=(tree[pos].l+tree[pos].r)/2;
    if((ln[tree[pos].bst].k==ln[num].k)&&(ln[tree[pos].bst].b==ln[num].b)) return;
    if(ln[tree[pos].bst].k*mid+ln[tree[pos].bst].b>ln[num].k*mid+ln[num].b) swap(tree[pos].bst,num);
    if(tree[pos].l==tree[pos].r) return;
    if(ln[num].k*tree[pos].l+ln[num].b<ln[tree[pos].bst].k*tree[pos].l+ln[tree[pos].bst].b) upd(pos*2,num);
    if(ln[num].k*tree[pos].r+ln[num].b<ln[tree[pos].bst].k*tree[pos].r+ln[tree[pos].bst].b) upd(pos*2+1,num);
}
int ask(int pos,int kk){
    if(kk<tree[pos].l||tree[pos].r<kk) return INF;
    if(tree[pos].l==tree[pos].r) return ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b;
    return min(min(ask(pos*2,kk),ask(pos*2+1,kk)),ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b);
}
int w[N],h[N],f[N];
int n,cnt,maxn,minn=INF;
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        maxn=max(maxn,h[i]);
    }
    for(int i=1;i<=n;i++){
        cin>>w[i];
        w[i]+=w[i-1];
    }
    build(1,0,maxn);
    ln[++cnt]={0,INF};
    upd(1,cnt);
    ln[++cnt]={-2*h[1],h[1]*h[1]-w[1]};
    upd(1,cnt);
    for(int i=2;i<=n;i++){   
        /*if(h[i]!=0)*/ f[i]=ask(1,h[i])+h[i]*h[i]+w[i-1];
        //else f[i]=minn+w[i-1];
        minn=min(minn,f[i]+h[i]*h[i]-w[i]);
        ln[++cnt]={-2*h[i],f[i]+h[i]*h[i]-w[i]};
        upd(1,cnt);
    }
    cout<<f[n];
    return 0;
}

by misaka_sama @ 2024-05-28 07:22:18

编号为0的线段的b初值要赋为正无穷

by toolong114514 @ 2024-05-28 14:19:20

@misaka_sama 加了

    ln[++cnt]={0,INF};
    upd(1,cnt);

by misaka_sama @ 2024-05-28 14:22:04

@toolong114514 然而你这样是错的，帮你调过了

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
#define int long long
const int INF=1e18;
const double eps=1e-10;
const int N=1e6+10;
struct node{
    int l,r,bst;
}tree[4*N];
struct ccf{
    int k,b;
}ln[N];
void build(int pos,int lft,int rgt){
    tree[pos].l=lft;
    tree[pos].r=rgt;
    if(lft==rgt) return;
    int mid=(lft+rgt)/2;
    build(pos*2,lft,mid);
    build(pos*2+1,mid+1,rgt);
}
void upd(int pos,int num){
    int mid=(tree[pos].l+tree[pos].r)/2;
    if((ln[tree[pos].bst].k==ln[num].k)&&(ln[tree[pos].bst].b==ln[num].b)) return;
    if(ln[tree[pos].bst].k*mid+ln[tree[pos].bst].b>ln[num].k*mid+ln[num].b) swap(tree[pos].bst,num);
    if(tree[pos].l==tree[pos].r) return;
    if(ln[num].k*tree[pos].l+ln[num].b<ln[tree[pos].bst].k*tree[pos].l+ln[tree[pos].bst].b) upd(pos*2,num);
    if(ln[num].k*tree[pos].r+ln[num].b<ln[tree[pos].bst].k*tree[pos].r+ln[tree[pos].bst].b) upd(pos*2+1,num);
}
int ask(int pos,int kk){
    if(kk<tree[pos].l||tree[pos].r<kk) return INF;
    if(tree[pos].l==tree[pos].r) return ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b;
    return min(min(ask(pos*2,kk),ask(pos*2+1,kk)),ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b);
}
int w[N],h[N],f[N];
int n,cnt,maxn,minn=INF;
signed main(){
    ln[0].b=INF;
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        maxn=max(maxn,h[i]);
    }
    for(int i=1;i<=n;i++){
        cin>>w[i];
        w[i]+=w[i-1];
    }
    build(1,0,maxn);
    ln[++cnt]={-2*h[1],h[1]*h[1]-w[1]};
    upd(1,cnt);
    for(int i=2;i<=n;i++){   
        f[i]=ask(1,h[i])+h[i]*h[i]+w[i-1];
        // minn=min(minn,f[i]+h[i]*h[i]-w[i]);
        ln[++cnt]={-2*h[i],f[i]+h[i]*h[i]-w[i]};
        upd(1,cnt);
    }
    cout<<f[n];
    return 0;
}

by toolong114514 @ 2024-05-28 15:14:23

@misaka_sama 过了，感谢Misaka大佬%%%

by toolong114514 @ 2024-05-28 15:14:47

此贴结