QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#37993 | #1880. Nikanor Loves Games | yzhang | RE | 0ms | 0kb | C++ | 2.5kb | 2022-07-03 18:07:17 | 2022-07-03 18:07:19 |
Judging History
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;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
2 1 4 15 3 5 10