求助!!全WA
查看原帖
求助!!全WA
254491
橙橙like海绵楼主2023/3/5 21:51
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=5e6+10;
const int inf=0x3f3f3f3f;
int m,n,tot,tr[N<<2];
double k[N],b[N];
inline ll read(){
    ll s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
double f(int num,int x){return k[num]*(x-1)+b[num];}
void change(int p,int l,int r,int x){
    if(l==r){
        if(f(x,l)>f(tr[p],l)) tr[p]=x;
        return ;   
    }
    if(!tr[p]){tr[p]=x;return ;}
    else{
        int mid=(l+r)>>1;
        double s1=f(x,l),s2=f(tr[p],l);
        if(k[x]>k[tr[p]]){
            if(s1>s2) change(p<<1,l,mid,tr[p]),tr[p]=x;
            else change(p<<1|1,mid+1,r,x);
        }
        else if(k[x]<k[tr[p]]){
            if(s1>s2) change(p<<1|1,mid+1,r,x),tr[p]=x;
            else change(p<<1,l,mid,x);
        }
        else if(b[x]>b[tr[p]]) tr[p]=x;
    }
}
double query(int p,int l,int r,int x){
    //if(l>x||x>r) return 0;
    if(l==r&&l==x) return f(tr[p],x);
    int mid=(l+r)>>1;
    double res=f(tr[p],x);
    if(x<=mid) res=max(res,query(p<<1,l,mid,x));
    else res=max(res,query(p<<1|1,mid+1,r,x));
    return res;
}
int main(){
    m=read();n=N-1;
    string op;
    int u;
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op[0]=='P'){
            tot++;
            std::cin>>b[tot]>>k[tot];
            //scanf("%lf%lf",&b[tot],&k[tot]);
            change(1,1,n,tot);
        }
        else {
            u=read();
            if(!tot) puts("0");
            printf("%d\n",(int)(query(1,1,n,u)/100));
        }
    }
    return 0;
}
2023/3/5 21:51
加载中...