QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618935#1880. Nikanor Loves Gamesydzr00000WA 0ms3960kbC++172.0kb2024-10-07 11:57:332024-10-07 11:57:33

Judging History

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

  • [2024-10-07 11:57:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3960kb
  • [2024-10-07 11:57:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Line{
	ll k,b;
};
inline ll func(const Line &L,const ll &x)
{
	return L.k*x+L.b;
}
class SegmentTree{
	private:
		struct node{
			Line L;
			int ls,rs;
		}seg[5000001];
		int tot=0;
	public:
		int root=0;
		inline void Update(int &id,ll l,ll r,Line L)
		{
			if(!id)
			{
				id=(++tot);
				seg[id].L=L;
				return;
			}
			if(l==r)
			{
				ll x=func(seg[id].L,l),y=func(L,l);
				if(y<x)
					seg[id].L=L;
				return;
			}
			if(func(L,l)>=func(seg[id].L,l)&&func(L,r)>=func(seg[id].L,r))
			{
				seg[id].L=L;
				return;
			}
			if(func(L,l)<func(seg[id].L,l)&&func(L,r)<func(seg[id].L,r))
				return;
			ll mid=(l+r)/2;
			if(L.k<seg[id].L.k)
			{
				if(func(L,mid)>=func(seg[id].L,mid))
				{
					Update(seg[id].ls,l,mid,seg[id].L);
					seg[id].L=L;
				}
				else
					Update(seg[id].rs,mid+1,r,L);
			}
			else
			{
				if(func(L,mid)>=func(seg[id].L,mid))
				{
					Update(seg[id].rs,mid+1,r,seg[id].L);
					seg[id].L=L;
				}
				else 
					Update(seg[id].ls,l,mid,L);
			}
		}
		inline ll Query(int id,ll l,ll r,ll x)
		{
			if(!id)
				return (ll)(-1e18);
			if(l==r)
				return func(seg[id].L,x);
			ll mid=(l+r)/2;
			return max(func(seg[id].L,x),(x<=mid?Query(seg[id].ls,l,mid,x):Query(seg[id].rs,mid+1,r,x)));
		}
};
SegmentTree S;
vector<tuple<int,int>>event;
const int V=1e9;
int main(){
    int n;
    scanf("%d",&n);
    long long start=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,x;
        scanf("%d %d %d",&a,&b,&x);
        start-=x;x*=2;
        event.push_back({a,x});
        event.push_back({b,x});
    }
    sort(event.begin(),event.end());
    long long w=0;
    for(auto [tim,paid]: event)
    {
        w+=paid;
        S.Update(S.root,1,V,{-4*tim,w});
    }
    w=0;
    double ans=-1e18;
    for(auto [tim,paid]: event)
    {
        w+=paid;
        ans=max(ans,start+(w+S.Query(S.root,1,V,tim))/4.00);
    }
    printf("%.10lf\n",ans);

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3892kb

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

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: 0ms
memory: 3876kb

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

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

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: 0ms
memory: 3872kb

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: 0ms
memory: 3956kb

input:

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

output:

-3.0000000000

result:

wrong answer 1st numbers differ - expected: '4.5000000', found: '-3.0000000', error = '1.6666667'