QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#37994#1880. Nikanor Loves GamesyzhangWA 2ms16020kbC++2.4kb2022-07-03 18:07:412022-07-03 18:07:42

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:42]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:16020kb
  • [2022-07-03 18:07:41]
  • 提交

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()
{
    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: 100
Accepted
time: 0ms
memory: 15996kb

input:

2
1 4 15
3 5 10

output:

2.50

result:

ok found '2.5000000', expected '2.5000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 16020kb

input:

1
2 2 8

output:

4.00

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 15968kb

input:

3
94 68 49
51 2 63
26 85 20

output:

-94.00

result:

wrong answer 1st numbers differ - expected: '-73.0000000', found: '-94.0000000', error = '0.2876712'