QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#601751#1880. Nikanor Loves Gamesrotcar07WA 1ms8132kbC++201.2kb2024-09-30 12:12:532024-09-30 12:12:54

Judging History

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

  • [2024-09-30 12:12:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8132kb
  • [2024-09-30 12:12:53]
  • 提交

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';
}

詳細信息

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'