QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #618940 | #1880. Nikanor Loves Games | ydzr00000 | WA | 0ms | 3952kb | C++17 | 2.0kb | 2024-10-07 11:59:22 | 2024-10-07 11:59:23 |
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,{-4ll*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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3904kb
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: 3892kb
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: 3896kb
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: 3948kb
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: 3844kb
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: 3912kb
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: 0
Accepted
time: 0ms
memory: 3888kb
input:
5 1 5 2 4 2 7 2 2 2 2 5 14 1 4 2
output:
4.5000000000
result:
ok found '4.5000000', expected '4.5000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
5 4 1 9 1 5 13 3 6 10 6 5 8 3 5 5
output:
9.0000000000
result:
ok found '9.0000000', expected '9.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
5 3 7 9 5 7 12 4 6 13 3 6 6 2 1 2
output:
-6.0000000000
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
10 8 10 26 11 2 28 13 4 13 11 1 26 6 15 23 12 8 7 9 8 11 11 10 17 8 11 18 3 10 27
output:
32.0000000000
result:
ok found '32.0000000', expected '32.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
10 6 5 10 10 15 21 7 2 30 14 6 12 1 11 6 1 13 19 8 13 29 9 4 14 1 4 29 4 12 17
output:
12.0000000000
result:
ok found '12.0000000', expected '12.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
10 5 15 15 3 14 20 11 14 26 15 12 22 5 15 11 12 10 10 1 12 18 7 7 14 3 5 10 12 9 23
output:
-6.0000000000
result:
ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
10 3 9 29 9 5 27 14 13 21 3 15 15 14 11 24 9 14 22 9 3 20 12 15 27 5 13 21 13 11 14
output:
-5.0000000000
result:
ok found '-5.0000000', expected '-5.0000000', error '-0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
10 3 13 11 3 5 20 9 10 1 5 5 25 10 1 29 6 10 26 1 15 1 10 10 18 6 6 2 14 6 20
output:
21.0000000000
result:
ok found '21.0000000', expected '21.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
100 68 91 90 56 38 71 69 57 87 80 62 21 31 80 25 36 48 40 71 66 49 15 57 78 96 69 43 25 73 57 86 13 5 23 98 18 83 94 9 8 22 43 46 3 50 81 11 26 14 35 39 49 68 73 41 11 25 35 47 48 5 96 15 15 56 60 42 1 40 11 4 25 57 72 9 43 3 90 16 45 36 83 50 17 55 40 39 72 37 6 70 84 24 12 36 95 43 15 13 82 28 68 ...
output:
35.5000000000
result:
ok found '35.5000000', expected '35.5000000', error '0.0000000'
Test #16:
score: -100
Wrong Answer
time: 0ms
memory: 3952kb
input:
100 92 35 39 34 92 36 45 45 46 66 5 64 22 21 48 53 70 91 93 19 98 97 67 54 57 77 64 90 81 23 12 83 92 59 3 26 13 65 47 19 23 58 27 58 38 60 18 70 32 94 53 100 66 97 33 53 16 56 2 64 8 9 55 93 92 22 27 25 39 45 49 24 76 80 89 73 55 77 69 53 90 39 77 40 86 12 11 23 87 25 8 96 31 73 45 98 52 62 55 98 9...
output:
-168.0000000000
result:
wrong answer 1st numbers differ - expected: '-100.0000000', found: '-168.0000000', error = '0.6800000'