QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601755 | #1880. Nikanor Loves Games | rotcar07 | RE | 41ms | 9040kb | C++20 | 1.2kb | 2024-09-30 12:16:54 | 2024-09-30 12:16:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=2e5+5;
int a[N],b[N],x[N],n,tp;
ll sum[N];int st[N];
typedef __int128 I;
int main(){
std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;vector<int> v;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>x[i];
v.push_back(a[i]),v.push_back(b[i]);
}
v.push_back(1);
sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
ll ans=-3e18;
for(int i=1;i<=n;i++){
sum[0]-=2*x[i];
sum[lower_bound(v.begin(),v.end(),a[i])-v.begin()]+=2*x[i];
sum[lower_bound(v.begin(),v.end(),b[i])-v.begin()]+=2*x[i];
}
int m=v.size()-1;
for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
st[++tp]=m;
for(int i=m-1;~i;i--){
while(tp>1&&I(sum[i]-sum[st[tp]])*(v[st[tp]]-v[st[tp-1]])<=I(sum[st[tp]]-sum[st[tp-1]])*(v[i]-v[st[tp]])) tp--;
st[++tp]=i;
}
for(int i=m;~i;i--){
auto calc=[&](int w){return sum[i]+sum[w]-v[w]*4ll*v[i];};
while(tp>1&&calc(st[tp])<=calc(st[tp-1]))tp--;
ans=max(ans,calc(st[tp]));
}
cout<<fixed<<setprecision(10)<<ans/4.0<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8000kb
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: 1ms
memory: 5836kb
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: 1ms
memory: 7776kb
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: 5876kb
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: 5992kb
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: 1ms
memory: 5904kb
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: 1ms
memory: 8028kb
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: 5876kb
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: 1ms
memory: 6084kb
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: 1ms
memory: 5872kb
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: 1ms
memory: 6092kb
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: 1ms
memory: 5904kb
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: 1ms
memory: 5880kb
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: 1ms
memory: 5968kb
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: 1ms
memory: 5876kb
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: 0
Accepted
time: 1ms
memory: 5840kb
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:
-100.0000000000
result:
ok found '-100.0000000', expected '-100.0000000', error '-0.0000000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5764kb
input:
100 20 84 93 15 45 13 28 33 2 49 41 12 12 50 59 62 89 49 11 60 42 74 84 33 14 94 85 51 2 89 26 66 87 92 12 26 47 32 84 34 16 80 20 16 27 48 34 14 54 61 66 52 47 21 41 87 3 81 45 68 24 18 94 71 23 87 12 49 34 79 6 6 91 92 56 3 15 64 22 69 41 91 3 60 21 76 79 65 41 48 46 9 35 34 54 92 68 10 1 22 82 17...
output:
25.5000000000
result:
ok found '25.5000000', expected '25.5000000', error '0.0000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 5832kb
input:
100 44 28 47 89 7 89 7 21 57 27 92 56 14 96 86 79 11 7 29 4 95 56 93 16 71 2 6 100 14 59 53 32 82 24 20 35 73 7 22 44 9 91 5 70 24 31 41 50 72 19 80 100 44 46 33 26 94 2 4 72 27 35 29 49 54 44 92 73 33 13 55 92 6 3 31 37 76 47 75 77 87 44 33 80 63 48 51 12 90 66 83 17 46 99 59 78 76 61 35 39 52 91 9...
output:
-57.0000000000
result:
ok found '-57.0000000', expected '-57.0000000', error '-0.0000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 7912kb
input:
100 68 73 96 63 60 58 86 13 29 13 32 95 4 25 97 96 30 61 55 57 43 34 98 95 32 14 27 65 26 38 79 10 69 56 33 35 98 82 59 55 9 5 82 25 12 19 53 94 90 82 6 48 29 70 29 60 76 23 59 89 38 44 64 31 81 10 77 96 24 51 99 79 25 19 11 68 32 34 28 89 38 100 64 4 94 16 19 58 40 89 17 34 57 64 69 80 92 12 81 63 ...
output:
-81.5000000000
result:
ok found '-81.5000000', expected '-81.5000000', error '-0.0000000'
Test #20:
score: 0
Accepted
time: 36ms
memory: 7668kb
input:
200000 14 11 10 2 6 10 18 13 7 8 5 11 13 5 14 16 14 2 4 5 17 4 20 7 7 3 9 9 8 11 15 1 20 19 13 3 19 17 15 9 16 20 5 5 15 2 1 6 11 14 13 8 13 7 2 3 10 7 18 9 1 4 12 17 3 7 14 4 17 12 14 11 18 11 6 11 7 15 10 4 13 13 2 14 2 1 18 7 3 18 12 16 19 17 13 7 7 17 1 20 9 2 2 1 2 6 13 11 7 11 9 20 16 3 9 4 4 ...
output:
2100856.0000000000
result:
ok found '2100856.0000000', expected '2100856.0000000', error '0.0000000'
Test #21:
score: 0
Accepted
time: 41ms
memory: 8100kb
input:
200000 18 20 15 4 20 7 1 5 6 6 8 19 3 2 5 14 17 17 2 18 18 17 18 10 8 11 11 6 9 2 1 19 11 16 18 7 13 8 13 7 9 2 6 4 12 6 9 10 5 5 6 16 2 15 18 18 1 8 9 1 8 10 11 14 18 12 19 8 8 18 11 17 9 19 1 17 3 2 3 11 15 9 17 10 12 17 6 14 17 20 10 16 11 18 2 6 16 5 3 4 2 16 3 16 16 16 11 14 4 2 4 5 8 6 17 8 9 ...
output:
2101118.0000000000
result:
ok found '2101118.0000000', expected '2101118.0000000', error '0.0000000'
Test #22:
score: 0
Accepted
time: 38ms
memory: 9040kb
input:
200000 6 4 9 1 13 15 16 13 6 13 8 19 5 11 12 11 3 11 4 19 6 3 7 9 9 20 12 3 17 12 4 6 6 8 3 8 19 3 6 14 13 13 19 18 20 13 20 10 3 20 4 4 11 15 15 12 12 9 16 9 20 7 6 12 1 17 4 11 7 12 16 4 8 11 17 11 19 5 16 3 14 5 3 18 15 17 17 20 7 19 8 9 18 7 12 16 12 12 17 8 11 10 4 19 11 18 18 17 13 9 12 10 20 ...
output:
2100494.0000000000
result:
ok found '2100494.0000000', expected '2100494.0000000', error '0.0000000'
Test #23:
score: 0
Accepted
time: 36ms
memory: 8540kb
input:
200000 10 4 6 3 15 8 20 17 1 15 3 10 16 12 3 12 2 13 7 4 19 5 16 12 18 20 9 16 17 2 6 4 17 4 16 16 13 18 8 5 6 7 4 13 17 17 12 10 17 10 6 16 16 4 7 19 19 14 11 13 3 4 5 10 13 15 5 15 6 10 4 18 11 2 4 1 15 7 1 11 4 14 17 2 10 9 5 7 16 2 18 1 5 12 1 10 20 3 19 16 20 4 5 14 17 19 17 16 9 4 11 14 12 15 ...
output:
2104832.0000000000
result:
ok found '2104832.0000000', expected '2104832.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 32ms
memory: 7996kb
input:
200000 14 9 12 13 9 5 7 10 8 13 7 10 6 2 10 9 4 3 9 12 7 3 6 11 15 12 10 1 10 9 12 19 4 17 4 16 6 5 5 19 7 6 1 3 6 20 3 14 15 5 20 7 10 4 11 13 10 15 2 5 14 13 16 12 8 20 6 15 17 4 17 20 7 18 3 12 15 10 14 19 19 10 8 6 1 1 9 14 6 4 12 2 16 13 10 4 8 15 13 20 1 19 2 1 11 5 8 15 14 16 15 19 8 18 9 19 ...
output:
2103344.0000000000
result:
ok found '2103344.0000000', expected '2103344.0000000', error '0.0000000'
Test #25:
score: 0
Accepted
time: 37ms
memory: 8504kb
input:
200000 18 17 6 14 18 10 18 18 4 15 7 14 20 3 1 18 19 6 7 17 8 8 19 7 16 20 11 18 10 19 18 13 4 13 17 20 12 20 3 6 20 20 6 18 19 20 15 18 17 12 13 11 15 4 7 11 12 16 13 14 18 10 15 14 19 1 15 2 16 18 6 11 6 2 19 2 15 17 11 15 1 6 14 13 4 5 1 20 11 3 10 6 4 18 19 19 5 18 3 17 15 5 3 8 6 11 6 2 10 11 1...
output:
2099791.0000000000
result:
ok found '2099791.0000000', expected '2099791.0000000', error '0.0000000'
Test #26:
score: 0
Accepted
time: 40ms
memory: 8456kb
input:
200000 6 17 15 12 20 7 6 18 19 2 18 17 6 16 8 15 1 16 5 2 16 6 8 6 13 9 8 15 2 17 12 3 15 5 18 4 18 11 5 13 12 15 19 12 15 20 6 14 15 10 7 7 12 17 19 6 19 1 8 18 5 15 15 16 2 19 4 6 7 12 11 13 1 13 6 16 19 4 16 19 16 2 20 17 19 13 13 7 5 2 4 3 15 7 16 13 13 9 17 1 4 19 4 15 8 17 13 5 15 2 18 5 12 11...
output:
2097689.0000000000
result:
ok found '2097689.0000000', expected '2097689.0000000', error '0.0000000'
Test #27:
score: 0
Accepted
time: 40ms
memory: 8304kb
input:
200000 6 10 9 9 13 3 1 6 19 20 18 1 17 9 7 12 20 18 7 15 9 4 17 9 10 9 10 15 3 8 18 2 2 18 7 8 3 6 18 11 13 13 15 11 4 7 14 18 13 17 1 15 13 13 15 20 10 2 15 10 16 16 10 13 17 20 17 6 6 2 8 19 16 9 5 6 20 7 10 7 7 14 11 5 14 9 16 9 15 20 2 15 18 20 5 7 9 8 19 17 1 13 5 10 3 3 12 20 12 18 17 14 17 2 ...
output:
2104030.0000000000
result:
ok found '2104030.0000000', expected '2104030.0000000', error '0.0000000'
Test #28:
score: 0
Accepted
time: 40ms
memory: 7412kb
input:
200000 14 14 19 19 15 8 4 18 14 2 17 9 11 7 18 9 6 8 9 15 9 1 11 8 11 17 11 16 15 14 16 12 1 10 20 13 17 5 20 18 10 12 20 5 13 11 18 2 7 16 14 3 2 5 7 18 17 3 6 18 20 10 9 11 8 5 6 13 5 16 12 6 11 1 5 17 16 14 3 3 13 7 1 17 13 9 8 20 4 7 19 16 5 5 11 1 17 16 1 17 14 7 6 1 1 9 2 3 16 5 1 7 9 5 13 3 1...
output:
2098865.0000000000
result:
ok found '2098865.0000000', expected '2098865.0000000', error '0.0000000'
Test #29:
score: 0
Accepted
time: 41ms
memory: 7540kb
input:
200000 14 1 14 8 20 15 2 15 11 20 16 8 3 15 5 20 19 2 1 18 11 8 16 7 4 17 12 14 15 17 8 9 10 5 20 10 2 4 11 15 20 19 20 15 16 14 13 14 5 17 15 17 3 7 8 8 7 3 8 14 19 6 13 4 15 19 10 18 9 7 20 17 5 8 8 7 6 6 18 3 15 2 17 14 3 17 5 11 2 19 12 20 10 10 5 2 7 18 9 13 11 12 20 13 15 12 20 2 15 17 3 13 18...
output:
2102647.0000000000
result:
ok found '2102647.0000000', expected '2102647.0000000', error '0.0000000'
Test #30:
score: -100
Runtime Error
input:
200000 558273441 797132086 95394395 410375788 603346154 991788394 501822655 954838746 104557620 987594944 800261563 456008910 944698458 473660405 947257686 43525951 515134254 221154267 581712330 247867513 268703732 553202136 786196487 556214428 384021989 736444004 231738414 760952860 568578734 24958...