QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601751 | #1880. Nikanor Loves Games | rotcar07 | WA | 1ms | 8132kb | C++20 | 1.2kb | 2024-09-30 12:12:53 | 2024-09-30 12:12:54 |
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(0);
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[1]-=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=1;i<=m;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: 7944kb
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: 8132kb
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: 7872kb
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: 1ms
memory: 5968kb
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: 1ms
memory: 5804kb
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: 5872kb
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: 5872kb
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: 8132kb
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: 5904kb
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: -100
Wrong Answer
time: 0ms
memory: 5820kb
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:
9.5000000000
result:
wrong answer 1st numbers differ - expected: '32.0000000', found: '9.5000000', error = '0.7031250'