QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#58251#1880. Nikanor Loves GamestricyzhkxWA 141ms21724kbC++141.1kb2022-10-25 11:31:532022-10-25 11:31:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-25 11:31:56]
  • 评测
  • 测评结果：WA
  • 用时：141ms
  • 内存：21724kb
查看
  • [2022-10-25 11:31:53]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200010],b[200010],w[200010],xx[400010];
ll f[200010];
struct Point
{
	ll x,y;
	Point(ll _x=0,ll _y=0):x(_x),y(_y){}
	Point operator-(const Point &a)const{return Point(x-a.x,y-a.y);}
	ll operator*(const Point &a)const{return x*a.y-y*a.x;}
	ll calc(ll k){return y-k*x;}
}c[400010],stk[400010];
int main()
{
	int n,len=0,tp=0;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&w[i]),xx[++len]=a[i],xx[++len]=b[i];
	xx[++len]=1;
	sort(xx+1,xx+len+1);
	len=unique(xx+1,xx+len+1)-xx-1;
	auto get=[&](int x){return lower_bound(xx+1,xx+len+1,x)-xx;};
	for(int i=1;i<=n;i++) a[i]=get(a[i]),b[i]=get(b[i]);
	for(int i=1;i<=n;i++) f[1]-=w[i],f[a[i]]+=w[i],f[b[i]]+=w[i];
	for(int i=1;i<=len;i++) f[i]+=f[i-1],c[i]=Point(xx[i],f[i]);
	for(int i=1;i<=len;i++)
	{
		while(tp>1 && (c[i]-stk[tp])*(stk[tp]-stk[tp-1])<=0) tp--;
		stk[++tp]=c[i];
	}
	int cur=tp;
	ll ans=-1e18;
	for(int i=1;i<=len;i++)
	{
		while(cur>1 && stk[cur].calc(2*xx[i])<stk[cur-1].calc(2*xx[i])) cur--;
		ans=max(ans,f[i]+stk[cur].calc(2*xx[i]));
	}
	printf("%.1lf\n",ans/2.);
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 16220kb

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: 8ms
memory: 16220kb

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

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

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: 4ms
memory: 16284kb

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

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: 3ms
memory: 16160kb

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

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

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

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

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

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

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

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: 6ms
memory: 16296kb

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: 0
Accepted
time: 3ms
memory: 16440kb

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:

-100.0

result:

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

Test #17:

score: 0
Accepted
time: 2ms
memory: 16308kb

input:

100
20 84 93
15 45 13
28 33 2
49 41 12
12 50 59
62 89 49
11 60 42
74 84 33
14 94 85
51 2 89
26 66 87
92 12 26
47 32 84
34 16 80
20 16 27
48 34 14
54 61 66
52 47 21
41 87 3
81 45 68
24 18 94
71 23 87
12 49 34
79 6 6
91 92 56
3 15 64
22 69 41
91 3 60
21 76 79
65 41 48
46 9 35
34 54 92
68 10 1
22 82 17...

output:

25.5

result:

ok found '25.5000000', expected '25.5000000', error '0.0000000'

Test #18:

score: 0
Accepted
time: 0ms
memory: 16372kb

input:

100
44 28 47
89 7 89
7 21 57
27 92 56
14 96 86
79 11 7
29 4 95
56 93 16
71 2 6
100 14 59
53 32 82
24 20 35
73 7 22
44 9 91
5 70 24
31 41 50
72 19 80
100 44 46
33 26 94
2 4 72
27 35 29
49 54 44
92 73 33
13 55 92
6 3 31
37 76 47
75 77 87
44 33 80
63 48 51
12 90 66
83 17 46
99 59 78
76 61 35
39 52 91
9...

output:

-57.0

result:

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

Test #19:

score: 0
Accepted
time: 7ms
memory: 16164kb

input:

100
68 73 96
63 60 58
86 13 29
13 32 95
4 25 97
96 30 61
55 57 43
34 98 95
32 14 27
65 26 38
79 10 69
56 33 35
98 82 59
55 9 5
82 25 12
19 53 94
90 82 6
48 29 70
29 60 76
23 59 89
38 44 64
31 81 10
77 96 24
51 99 79
25 19 11
68 32 34
28 89 38
100 64 4
94 16 19
58 40 89
17 34 57
64 69 80
92 12 81
63 ...

output:

-81.5

result:

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

Test #20:

score: 0
Accepted
time: 53ms
memory: 20172kb

input:

200000
14 11 10
2 6 10
18 13 7
8 5 11
13 5 14
16 14 2
4 5 17
4 20 7
7 3 9
9 8 11
15 1 20
19 13 3
19 17 15
9 16 20
5 5 15
2 1 6
11 14 13
8 13 7
2 3 10
7 18 9
1 4 12
17 3 7
14 4 17
12 14 11
18 11 6
11 7 15
10 4 13
13 2 14
2 1 18
7 3 18
12 16 19
17 13 7
7 17 1
20 9 2
2 1 2
6 13 11
7 11 9
20 16 3
9 4 4
...

output:

2100856.0

result:

ok found '2100856.0000000', expected '2100856.0000000', error '0.0000000'

Test #21:

score: 0
Accepted
time: 57ms
memory: 20184kb

input:

200000
18 20 15
4 20 7
1 5 6
6 8 19
3 2 5
14 17 17
2 18 18
17 18 10
8 11 11
6 9 2
1 19 11
16 18 7
13 8 13
7 9 2
6 4 12
6 9 10
5 5 6
16 2 15
18 18 1
8 9 1
8 10 11
14 18 12
19 8 8
18 11 17
9 19 1
17 3 2
3 11 15
9 17 10
12 17 6
14 17 20
10 16 11
18 2 6
16 5 3
4 2 16
3 16 16
16 11 14
4 2 4
5 8 6
17 8 9
...

output:

2101118.0

result:

ok found '2101118.0000000', expected '2101118.0000000', error '0.0000000'

Test #22:

score: 0
Accepted
time: 42ms
memory: 20200kb

input:

200000
6 4 9
1 13 15
16 13 6
13 8 19
5 11 12
11 3 11
4 19 6
3 7 9
9 20 12
3 17 12
4 6 6
8 3 8
19 3 6
14 13 13
19 18 20
13 20 10
3 20 4
4 11 15
15 12 12
9 16 9
20 7 6
12 1 17
4 11 7
12 16 4
8 11 17
11 19 5
16 3 14
5 3 18
15 17 17
20 7 19
8 9 18
7 12 16
12 12 17
8 11 10
4 19 11
18 18 17
13 9 12
10 20 ...

output:

2100494.0

result:

ok found '2100494.0000000', expected '2100494.0000000', error '0.0000000'

Test #23:

score: 0
Accepted
time: 52ms
memory: 20164kb

input:

200000
10 4 6
3 15 8
20 17 1
15 3 10
16 12 3
12 2 13
7 4 19
5 16 12
18 20 9
16 17 2
6 4 17
4 16 16
13 18 8
5 6 7
4 13 17
17 12 10
17 10 6
16 16 4
7 19 19
14 11 13
3 4 5
10 13 15
5 15 6
10 4 18
11 2 4
1 15 7
1 11 4
14 17 2
10 9 5
7 16 2
18 1 5
12 1 10
20 3 19
16 20 4
5 14 17
19 17 16
9 4 11
14 12 15
...

output:

2104832.0

result:

ok found '2104832.0000000', expected '2104832.0000000', error '0.0000000'

Test #24:

score: 0
Accepted
time: 49ms
memory: 20228kb

input:

200000
14 9 12
13 9 5
7 10 8
13 7 10
6 2 10
9 4 3
9 12 7
3 6 11
15 12 10
1 10 9
12 19 4
17 4 16
6 5 5
19 7 6
1 3 6
20 3 14
15 5 20
7 10 4
11 13 10
15 2 5
14 13 16
12 8 20
6 15 17
4 17 20
7 18 3
12 15 10
14 19 19
10 8 6
1 1 9
14 6 4
12 2 16
13 10 4
8 15 13
20 1 19
2 1 11
5 8 15
14 16 15
19 8 18
9 19 ...

output:

2103344.0

result:

ok found '2103344.0000000', expected '2103344.0000000', error '0.0000000'

Test #25:

score: 0
Accepted
time: 64ms
memory: 20260kb

input:

200000
18 17 6
14 18 10
18 18 4
15 7 14
20 3 1
18 19 6
7 17 8
8 19 7
16 20 11
18 10 19
18 13 4
13 17 20
12 20 3
6 20 20
6 18 19
20 15 18
17 12 13
11 15 4
7 11 12
16 13 14
18 10 15
14 19 1
15 2 16
18 6 11
6 2 19
2 15 17
11 15 1
6 14 13
4 5 1
20 11 3
10 6 4
18 19 19
5 18 3
17 15 5
3 8 6
11 6 2
10 11 1...

output:

2099791.0

result:

ok found '2099791.0000000', expected '2099791.0000000', error '0.0000000'

Test #26:

score: 0
Accepted
time: 54ms
memory: 20228kb

input:

200000
6 17 15
12 20 7
6 18 19
2 18 17
6 16 8
15 1 16
5 2 16
6 8 6
13 9 8
15 2 17
12 3 15
5 18 4
18 11 5
13 12 15
19 12 15
20 6 14
15 10 7
7 12 17
19 6 19
1 8 18
5 15 15
16 2 19
4 6 7
12 11 13
1 13 6
16 19 4
16 19 16
2 20 17
19 13 13
7 5 2
4 3 15
7 16 13
13 9 17
1 4 19
4 15 8
17 13 5
15 2 18
5 12 11...

output:

2097689.0

result:

ok found '2097689.0000000', expected '2097689.0000000', error '0.0000000'

Test #27:

score: 0
Accepted
time: 61ms
memory: 20172kb

input:

200000
6 10 9
9 13 3
1 6 19
20 18 1
17 9 7
12 20 18
7 15 9
4 17 9
10 9 10
15 3 8
18 2 2
18 7 8
3 6 18
11 13 13
15 11 4
7 14 18
13 17 1
15 13 13
15 20 10
2 15 10
16 16 10
13 17 20
17 6 6
2 8 19
16 9 5
6 20 7
10 7 7
14 11 5
14 9 16
9 15 20
2 15 18
20 5 7
9 8 19
17 1 13
5 10 3
3 12 20
12 18 17
14 17 2
...

output:

2104030.0

result:

ok found '2104030.0000000', expected '2104030.0000000', error '0.0000000'

Test #28:

score: 0
Accepted
time: 72ms
memory: 20056kb

input:

200000
14 14 19
19 15 8
4 18 14
2 17 9
11 7 18
9 6 8
9 15 9
1 11 8
11 17 11
16 15 14
16 12 1
10 20 13
17 5 20
18 10 12
20 5 13
11 18 2
7 16 14
3 2 5
7 18 17
3 6 18
20 10 9
11 8 5
6 13 5
16 12 6
11 1 5
17 16 14
3 3 13
7 1 17
13 9 8
20 4 7
19 16 5
5 11 1
17 16 1
17 14 7
6 1 1
9 2 3
16 5 1
7 9 5
13 3 1...

output:

2098865.0

result:

ok found '2098865.0000000', expected '2098865.0000000', error '0.0000000'

Test #29:

score: 0
Accepted
time: 58ms
memory: 20180kb

input:

200000
14 1 14
8 20 15
2 15 11
20 16 8
3 15 5
20 19 2
1 18 11
8 16 7
4 17 12
14 15 17
8 9 10
5 20 10
2 4 11
15 20 19
20 15 16
14 13 14
5 17 15
17 3 7
8 8 7
3 8 14
19 6 13
4 15 19
10 18 9
7 20 17
5 8 8
7 6 6
18 3 15
2 17 14
3 17 5
11 2 19
12 20 10
10 5 2
7 18 9
13 11 12
20 13 15
12 20 2
15 17 3
13 18...

output:

2102647.0

result:

ok found '2102647.0000000', expected '2102647.0000000', error '0.0000000'

Test #30:

score: -100
Wrong Answer
time: 141ms
memory: 21724kb

input:

200000
558273441 797132086 95394395
410375788 603346154 991788394
501822655 954838746 104557620
987594944 800261563 456008910
944698458 473660405 947257686
43525951 515134254 221154267
581712330 247867513 268703732
553202136 786196487 556214428
384021989 736444004 231738414
760952860 568578734 24958...

output:

4611674260591961088.0

result:

wrong answer 1st numbers differ - expected: '-999998979.0000000', found: '4611674260591961088.0000000', error = '4611678970.1161890'
English 繁體中文 简体中文

服务器时间: 2025-01-21 04:54:32 | 开源项目