QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#618935 | #1880. Nikanor Loves Games | ydzr00000 | WA | 0ms | 3960kb | C++17 | 2.0kb | 2024-10-07 11:57:33 | 2024-10-07 11:57:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Line{
ll k,b;
};
inline ll func(const Line &L,const ll &x)
{
return L.k*x+L.b;
}
class SegmentTree{
private:
struct node{
Line L;
int ls,rs;
}seg[5000001];
int tot=0;
public:
int root=0;
inline void Update(int &id,ll l,ll r,Line L)
{
if(!id)
{
id=(++tot);
seg[id].L=L;
return;
}
if(l==r)
{
ll x=func(seg[id].L,l),y=func(L,l);
if(y<x)
seg[id].L=L;
return;
}
if(func(L,l)>=func(seg[id].L,l)&&func(L,r)>=func(seg[id].L,r))
{
seg[id].L=L;
return;
}
if(func(L,l)<func(seg[id].L,l)&&func(L,r)<func(seg[id].L,r))
return;
ll mid=(l+r)/2;
if(L.k<seg[id].L.k)
{
if(func(L,mid)>=func(seg[id].L,mid))
{
Update(seg[id].ls,l,mid,seg[id].L);
seg[id].L=L;
}
else
Update(seg[id].rs,mid+1,r,L);
}
else
{
if(func(L,mid)>=func(seg[id].L,mid))
{
Update(seg[id].rs,mid+1,r,seg[id].L);
seg[id].L=L;
}
else
Update(seg[id].ls,l,mid,L);
}
}
inline ll Query(int id,ll l,ll r,ll x)
{
if(!id)
return (ll)(-1e18);
if(l==r)
return func(seg[id].L,x);
ll mid=(l+r)/2;
return max(func(seg[id].L,x),(x<=mid?Query(seg[id].ls,l,mid,x):Query(seg[id].rs,mid+1,r,x)));
}
};
SegmentTree S;
vector<tuple<int,int>>event;
const int V=1e9;
int main(){
int n;
scanf("%d",&n);
long long start=0;
for(int i=1;i<=n;i++)
{
int a,b,x;
scanf("%d %d %d",&a,&b,&x);
start-=x;x*=2;
event.push_back({a,x});
event.push_back({b,x});
}
sort(event.begin(),event.end());
long long w=0;
for(auto [tim,paid]: event)
{
w+=paid;
S.Update(S.root,1,V,{-4*tim,w});
}
w=0;
double ans=-1e18;
for(auto [tim,paid]: event)
{
w+=paid;
ans=max(ans,start+(w+S.Query(S.root,1,V,tim))/4.00);
}
printf("%.10lf\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
2 1 4 15 3 5 10
output:
2.5000000000
result:
ok found '2.5000000', expected '2.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
1 2 2 8
output:
4.0000000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
3 94 68 49 51 2 63 26 85 20
output:
-73.0000000000
result:
ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
2 14 68 12 28 2 46
output:
-16.0000000000
result:
ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
5 6 6 8 6 1 11 6 1 13 6 1 5 5 1 2
output:
9.5000000000
result:
ok found '9.5000000', expected '9.5000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
5 5 4 2 4 1 10 3 1 3 2 1 3 5 1 5
output:
5.5000000000
result:
ok found '5.5000000', expected '5.5000000', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3956kb
input:
5 1 5 2 4 2 7 2 2 2 2 5 14 1 4 2
output:
-3.0000000000
result:
wrong answer 1st numbers differ - expected: '4.5000000', found: '-3.0000000', error = '1.6666667'