QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#564895#1880. Nikanor Loves Gamesxzf_200906WA 1ms7832kbC++141.6kb2024-09-15 16:49:202024-09-15 16:49:21

Judging History

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

  • [2024-09-15 16:49:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7832kb
  • [2024-09-15 16:49:20]
  • 提交

answer

#include <bits/stdc++.h>
#define LL long long
using namespace std;
struct Event{
	int x,val;
	bool operator<(Event e){
		return x<e.x;
	}
}event[1000000];
struct Line{
	LL k,b;
	LL operator()(int x){
		return 1ll*k*x+b;
	}
}tree[1000000];
int ls[1000000],rs[1000000],tot=1;
void change(int p,int l,int r,Line line){
	if(tree[p](l)>=line(l)&&tree[p](r)>=line(r)) return;
	if(tree[p](l)<=line(l)&&tree[p](r)<=line(r)){
		tree[p]=line;
		return;
	}
	int mid=(l+r)>>1;
	if(ls[p]==0){
		ls[p]=++tot;
		tree[tot].b=-1000000000000ll;
	}
	change(ls[p],l,mid,line);
	if(rs[p]==0){
		rs[p]=++tot;
		tree[tot].b=-1000000000000ll;
	}
	change(rs[p],mid+1,r,line);
}
LL query(int p,int l,int r,int pos){
	if(p==0) return -1000000000000ll;
	int mid=(l+r)>>1;
	LL val=tree[p](pos);
	if(pos<=mid) return max(query(ls[p],l,mid,pos),val);
	else return max(query(rs[p],mid+1,r,pos),val);
}
Line li[1000000];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tree[1]={-4,0};
	int n;
	cin>>n;
	LL shift=0;
	for(int i=1;i<=n;i++){
		int a,b,x;
		cin>>a>>b>>x;
		shift-=x*2;
		event[i*2-1]={a,x};
		event[i*2]={b,x};
	}
	sort(event+1,event+n*2+1);
	LL sum=0,ans=LONG_LONG_MIN;
	for(int i=1;i<=n*2;i++){
		sum+=event[i].val;
		change(1,1,1000000000,{-2ll*event[i].x,sum});
	}
	sum=0;
	for(int i=1;i<=n*2;i++){
		sum+=event[i].val;
		ans=max(ans,sum+query(1,1,1000000000,event[i].x));
	}
	ans+=shift;
	if(ans<0){
		cout<<'-';
		ans=-ans;
	}
	cout<<(ans>>1)<<'.';
	if((ans&1)==0) cout<<"0\n";
	if((ans&1)==1) cout<<"5\n";
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7708kb

input:

2
1 4 15
3 5 10

output:

2.5

result:

ok found '2.5000000', expected '2.5000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7712kb

input:

1
2 2 8

output:

4.0

result:

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

Test #3:

score: 0
Accepted
time: 1ms
memory: 7796kb

input:

3
94 68 49
51 2 63
26 85 20

output:

-73.0

result:

ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 7792kb

input:

2
14 68 12
28 2 46

output:

-16.0

result:

ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 7792kb

input:

5
6 6 8
6 1 11
6 1 13
6 1 5
5 1 2

output:

9.5

result:

ok found '9.5000000', expected '9.5000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 7708kb

input:

5
5 4 2
4 1 10
3 1 3
2 1 3
5 1 5

output:

5.5

result:

ok found '5.5000000', expected '5.5000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7776kb

input:

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

output:

4.5

result:

ok found '4.5000000', expected '4.5000000', error '0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 7768kb

input:

5
4 1 9
1 5 13
3 6 10
6 5 8
3 5 5

output:

9.0

result:

ok found '9.0000000', expected '9.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 7772kb

input:

5
3 7 9
5 7 12
4 6 13
3 6 6
2 1 2

output:

-6.0

result:

ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 7796kb

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:

32.0

result:

ok found '32.0000000', expected '32.0000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 7708kb

input:

10
6 5 10
10 15 21
7 2 30
14 6 12
1 11 6
1 13 19
8 13 29
9 4 14
1 4 29
4 12 17

output:

12.0

result:

ok found '12.0000000', expected '12.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 1ms
memory: 7832kb

input:

10
5 15 15
3 14 20
11 14 26
15 12 22
5 15 11
12 10 10
1 12 18
7 7 14
3 5 10
12 9 23

output:

-6.0

result:

ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 7780kb

input:

10
3 9 29
9 5 27
14 13 21
3 15 15
14 11 24
9 14 22
9 3 20
12 15 27
5 13 21
13 11 14

output:

-5.0

result:

ok found '-5.0000000', expected '-5.0000000', error '-0.0000000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 7772kb

input:

10
3 13 11
3 5 20
9 10 1
5 5 25
10 1 29
6 10 26
1 15 1
10 10 18
6 6 2
14 6 20

output:

21.0

result:

ok found '21.0000000', expected '21.0000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 1ms
memory: 7792kb

input:

100
68 91 90
56 38 71
69 57 87
80 62 21
31 80 25
36 48 40
71 66 49
15 57 78
96 69 43
25 73 57
86 13 5
23 98 18
83 94 9
8 22 43
46 3 50
81 11 26
14 35 39
49 68 73
41 11 25
35 47 48
5 96 15
15 56 60
42 1 40
11 4 25
57 72 9
43 3 90
16 45 36
83 50 17
55 40 39
72 37 6
70 84 24
12 36 95
43 15 13
82 28 68
...

output:

35.5

result:

ok found '35.5000000', expected '35.5000000', error '0.0000000'

Test #16:

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

input:

100
92 35 39
34 92 36
45 45 46
66 5 64
22 21 48
53 70 91
93 19 98
97 67 54
57 77 64
90 81 23
12 83 92
59 3 26
13 65 47
19 23 58
27 58 38
60 18 70
32 94 53
100 66 97
33 53 16
56 2 64
8 9 55
93 92 22
27 25 39
45 49 24
76 80 89
73 55 77
69 53 90
39 77 40
86 12 11
23 87 25
8 96 31
73 45 98
52 62 55
98 9...

output:

-168.0

result:

wrong answer 1st numbers differ - expected: '-100.0000000', found: '-168.0000000', error = '0.6800000'