QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#601754#1880. Nikanor Loves Gamesrotcar07WA 1ms5996kbC++201.2kb2024-09-30 12:16:222024-09-30 12:16:23

Judging History

你现在查看的是最新测评结果

  • [2024-09-30 12:16:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5996kb
  • [2024-09-30 12:16:22]
  • 提交

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[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: 5888kb

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: 5936kb

input:

1
2 2 8

output:

4.0000000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 5996kb

input:

3
94 68 49
51 2 63
26 85 20

output:

0.0000000000

result:

wrong answer 1st numbers differ - expected: '-73.0000000', found: '0.0000000', error = '1.0000000'