QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #618942 | #1880. Nikanor Loves Games | ydzr00000 | WA | 0ms | 3952kb | C++17 | 2.0kb | 2024-10-07 12:00:20 | 2024-10-07 12:00:21 |
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: 3880kb
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: 3884kb
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: 3900kb
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: 3952kb
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: 3952kb
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: 3896kb
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: 3820kb
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: 3896kb
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: 3900kb
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: 3884kb
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: 3824kb
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: 3824kb
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: 3928kb
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: 3904kb
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: 3848kb
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'