QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#37993#1880. Nikanor Loves GamesyzhangRE 0ms0kbC++2.5kb2022-07-03 18:07:172022-07-03 18:07:19

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-03 18:07:19]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2022-07-03 18:07:17]
  • 提交

answer

//μ's forever
#include <bits/stdc++.h>
#define N 500005
#define ll long long
#define getchar nc
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void write(register int x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[20];register int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
int n,a[N],b[N],x[N],c[N<<1],tot;
ll pre[N<<1],del;
struct node{
    int opt,pos,v;
}t[N<<2];
int cnt;
bool cmp(node a,node b){
    if(a.pos==b.pos) return a.opt<b.opt;
    return a.pos<b.pos;
}
int pq[N<<1],hd,tl;
ll ans;
int main()
{
    freopen("gamble.in","r",stdin);
    // freopen("data3.in","r",stdin);
    freopen("gamble.out","w",stdout);

    n=read();
    for(int i=1;i<=n;++i){
        a[i]=read(),b[i]=read(),x[i]=read();
        if(a[i]<b[i]) swap(a[i],b[i]);
        c[++tot]=a[i],c[++tot]=b[i];
        ans-=x[i];
    }
    ans*=4;
    ans-=4;
    // cerr<<ans<<endl;
    c[++tot]=1;
    sort(c+1,c+1+tot);
    tot=unique(c+1,c+1+tot)-c-1;
    for(int i=1;i<=n;++i){
        a[i]=lower_bound(c+1,c+1+tot,a[i])-c;
        b[i]=lower_bound(c+1,c+1+tot,b[i])-c;
    }
    for(int i=1;i<=n;++i){
        pre[1]-=4ll*x[i];
        pre[a[i]]+=2*x[i];
        pre[b[i]]+=2*x[i];
    }
    for(int i=1;i<=tot;++i) pre[i]+=pre[i-1];
    // for(int i=1;i<=tot;++i) cerr<<pre[i]<<endl;
    for(int i=1;i<=tot;++i) t[++cnt]=(node){1,i,c[i]};
    for(int i=1;i<=n;++i){
        t[++cnt]=(node){0,a[i],2*x[i]};
        t[++cnt]=(node){0,b[i],2*x[i]};
    }
    sort(t+1,t+1+cnt,cmp);
    hd=0,tl=-1;
    for(int i=tot;i>=1;--i){
        while(hd<=tl&&pre[pq[tl]]<=pre[i]) --tl;
        pq[++tl]=i;
    }
    for(int i=1;i<=cnt;++i){
        if(t[i].opt==0) del+=t[i].v;
        else{
            int p=t[i].v;
            while(hd<tl&&-4ll*p*c[pq[hd]]+pre[pq[hd]]<=-4ll*p*c[pq[hd+1]]+pre[pq[hd+1]]) ++hd;
            // cerr<<p<<" "<<c[pq[hd]]<<" "<<pre[pq[hd]]<<" "<<del<<endl;
            // cerr<<-4ll*p*c[pq[hd]]+pre[pq[hd]]+del<<endl;
            ans=max(ans,-4ll*p*c[pq[hd]]+pre[pq[hd]]+del);
        }
    }
    printf("%.2lf\n",ans/4.0);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

2
1 4 15
3 5 10

output:


result: