QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#37994 | #1880. Nikanor Loves Games | yzhang | WA | 2ms | 16020kb | C++ | 2.4kb | 2022-07-03 18:07:41 | 2022-07-03 18:07:42 |
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()
{
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'