QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111954#1880. Nikanor Loves GameslingchenWA 2ms3748kbC++142.0kb2023-06-09 11:16:082023-06-09 11:16:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-09 11:16:10]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3748kb
  • [2023-06-09 11:16:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define mkp make_pair
const int N=5e5+10;
const int M=1e6+10;
int n,m;
int a[N],b[N];ll x[N];
vector<int>li; map<int,int>ma;
ll f[M]; ll w[M];
ll pre[N],sum;
pair<int,int>res[N];

namespace task1{
    void solve()
    {
        ll ans=-0x3f3f3f3f3f3f3f3f;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=m;j++) ans=max(ans,f[i]+f[j]-4ll*li[i]*li[j]);
        printf("%lld\n",ans);
    }
}

namespace task2{
    //b=val-f[a]  k=-4a  x=-b  y=f[b]
    db slope(int a,int b)
    {
        return (db)(f[b]-f[a])/(w[b]-w[a]);
    }
    int st[M],h,t;
    void solve()
    {
        ll ans=-0x3f3f3f3f3f3f3f3f;
        //printf("%lld\n",ans);
        for(int i=1;i<=m;i++) w[i]=li[i];
        h=1; st[++t]=1;
        //ans=max(ans,f[1]+f[2]-4ll*w[1]*w[2]);
        for(int i=2;i<=m;i++)
        {
            db k=(db)-4*w[i];
            while(h<t&&k>=slope(st[h],st[h+1])) h++;
            int j=st[h];
            ans=max(ans,f[j]+f[i]-4ll*w[i]*w[j]);
            while(h<t&&slope(st[t-1],i)<=slope(st[t-1],st[t])) t--;
            st[++t]=i;
        }
        for(int i=1;i<=m;i++) ans=max(ans,f[i]+f[i]-4ll*w[i]*w[i]);
        printf("%.10lf\n",ans/4.0);
    }
}

int main()
{
    //freopen("data3.in","r",stdin);
    //freopen("test.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d%lld",&a[i],&b[i],&x[i]);
    li.push_back(0); li.push_back(1);
    for(int i=1;i<=n;i++) li.push_back(a[i]),li.push_back(b[i]);
    sort(li.begin(),li.end());  
    li.erase(unique(li.begin(),li.end()),li.end());
    m=(int)li.size()-1;
    for(int i=1;i<=m;i++) ma[li[i]]=i;
    for(int i=1;i<=n;i++) a[i]=ma[a[i]],b[i]=ma[b[i]];
    for(int i=1;i<=n;i++) f[a[i]]+=2*x[i],f[b[i]]+=2*x[i],f[1]-=2*x[i];
    for(int i=1;i<=m;i++) f[i]+=f[i-1];
    //for(int i=1;i<=m;i++) printf("%lld ",li[i]);
    //if(n<=2000) {task1::solve(); return 0;}
    task2::solve();  fflush(stdout);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3528kb

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: 2ms
memory: 3620kb

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: 2ms
memory: 3624kb

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

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: 2ms
memory: 3560kb

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: 2ms
memory: 3576kb

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: -100
Wrong Answer
time: 1ms
memory: 3684kb

input:

5
1 5 2
4 2 7
2 2 2
2 5 14
1 4 2

output:

2.0000000000

result:

wrong answer 1st numbers differ - expected: '4.5000000', found: '2.0000000', error = '0.5555556'