QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116179#4144. 基站建设SnowNorth60 79ms19112kbC++141.7kb2023-06-28 11:25:262023-06-28 11:25:28

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-28 11:25:28]
  • 评测
  • 测评结果:60
  • 用时:79ms
  • 内存:19112kb
  • [2023-06-28 11:25:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;

double x[N], rd[N]{1}, v[N], f[N];
int q[N], tail, head;
int id[N], tmp[N];

double Y (int i) { return f[i] - x[i] * sqrt(rd[i]) / (rd[i] * 2); }
double X (int i) { return sqrt(rd[i]) / rd[i]; }
double slope_up (int i, int j) { return Y(i) - Y(j); }
double slope_down (int i, int j) { return X(i) - X(j); }

void dvd (int l, int r) {
	if (l == r) return ;
	int mid = (l + r) >> 1;
	dvd (l, mid);
	
	head = tail = 0;
	q[head] = 0;
	for (int i = l; i <= mid; i++) {
		while (head < tail && slope_up(q[tail], q[tail - 1]) * slope_down(id[i], q[tail]) >= slope_up(id[i], q[tail]) * slope_down(q[tail], q[tail - 1])) tail--;
		q[++tail] = id[i];
	}
	
	for (int i = r; i > mid; i--) {
		while (head < tail && slope_up(q[head + 1], q[head]) <= (-x[id[i]] / 2) * slope_down(q[head + 1], q[head])) head++;
		int j = q[head];
		f[id[i]] = min(f[id[i]], f[j] + v[id[i]] + (x[id[i]] - x[j]) / (sqrt(rd[j]) * 2));
	}
	
	dvd (mid + 1, r); 
	
	int p1 = l, p2 = mid + 1, pk = l;
	while (p1 <= mid || p2 <= r) {
		if (p2 > r || (p1 <= mid && X(id[p1]) <= X(id[p2]))) tmp[pk++] = id[p1++];
		else tmp[pk++] = id[p2++];
	}
	for (int i = l; i <= r; i++) id[i] = tmp[i];
}

void solve() {
	int n;
	double m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> rd[i] >> v[i];
		if (rd[i] == 0) { --i; --n; continue ; }
		id[i] = i;
	}
	
	for (int i = 0; i <= n; i++) f[i] = 1e14;
	f[id[1]] = v[id[1]];
	
	dvd (1, n);
	
	double ans = 1e14;
	for (int i = 1; i <= n; i++) {
		if (x[i] + rd[i] >= m) ans = min(ans, f[i]);
	}
	printf("%.3lf", ans);
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 3ms
memory: 13980kb

input:

1000 248898
379 966 5573
674 779 358
924 376 2936
1066 958 9121
1502 254 2106
1629 3 8415
1630 368 5333
1672 508 6388
1729 527 2753
2153 174 5500
2375 791 1290
2529 595 4016
2617 456 1691
2784 801 5672
3105 223 327
3172 337 102
3405 708 3634
3689 356 2453
4031 896 2949
4246 535 4778
4375 816 7037
44...

output:

11561.763

result:

ok single line: '11561.763'

Test #2:

score: 10
Accepted
time: 4ms
memory: 13916kb

input:

2000 1009425
860 952 5247
1771 1243 5679
1902 1082 3972
2285 1121 5994
2993 1253 2007
3863 1026 1921
4401 485 3646
5316 158 7864
6025 1443 2662
6066 1388 4151
6967 410 6641
7454 1242 3805
8204 1185 431
8603 1374 7611
8988 526 8129
9273 675 5837
9468 781 82
9916 306 7413
10444 250 9539
10775 270 5302...

output:

22583.431

result:

ok single line: '22583.431'

Test #3:

score: 10
Accepted
time: 27ms
memory: 16300kb

input:

30000 208261115
864 28571 1834
15485 12408 212
16594 9183 1748
25702 15920 4424
30991 6177 1810
35347 10436 5689
43947 27170 866
52883 5892 4169
63085 26807 5854
64703 9156 879
68956 13588 7353
77942 27113 7064
82404 24411 54
93858 204 6374
108740 24357 5258
117968 13553 943
120815 29010 1804
130438...

output:

606301.371

result:

ok single line: '606301.371'

Test #4:

score: 10
Accepted
time: 37ms
memory: 16492kb

input:

50000 521464011
9465 11023 8923
15123 14734 393
31578 38109 1936
38818 38492 3283
54952 7494 23
57653 35312 497
71831 48863 4431
72658 6086 3397
95627 45573 534
113000 14537 2071
123604 33183 5365
144848 3484 3886
158422 47748 3607
160664 47145 5806
164928 30546 2181
172661 22370 1669
184155 9687 56...

output:

1184951.390

result:

ok single line: '1184951.390'

Test #5:

score: 10
Accepted
time: 71ms
memory: 18852kb

input:

100000 1639535370
12980 73364 1188
43346 95781 8259
64974 26132 9360
86097 99075 1456
91274 66356 3257
112682 80107 5853
120878 89048 8102
125615 92357 1693
129130 92547 4325
151382 99569 597
180542 80444 2690
182515 34201 5375
211889 54344 3238
230903 86907 1980
255466 99177 4459
277879 92999 5910
...

output:

2597807.323

result:

ok single line: '2597807.323'

Test #6:

score: 10
Accepted
time: 79ms
memory: 19112kb

input:

100000 1637586710
8498 43078 592
37847 3343 6937
50426 95305 3666
72079 2174 3863
82110 43091 9302
93248 12219 2048
114072 93664 2800
118639 90789 4199
125559 76868 1854
141262 58071 1715
142014 98674 421
156871 89953 8904
162190 53121 3784
194286 83640 3232
206136 1300 5037
213268 76646 2780
233979...

output:

2592671.384

result:

ok single line: '2592671.384'

Test #7:

score: 0
Runtime Error

input:

5000000 12499985000004
2499997 1 5672
4999994 2 5672
7499991 3 5672
9999988 4 5672
12499985 5 5672
14999982 6 5672
17499979 7 5672
19999976 8 5672
22499973 9 5672
24999970 10 5672
27499967 11 5672
29999964 12 5672
32499961 13 5672
34999958 14 5672
37499955 15 5672
39999952 16 5672
42499949 17 5672
4...

output:


result:


Test #8:

score: 0
Runtime Error

input:

5000000 12499985000003
2499997 5000000 5672
4999994 1 5672
7499991 2 5672
9999988 3 5672
12499985 4 5672
14999982 5 5672
17499979 6 5672
19999976 7 5672
22499973 8 5672
24999970 9 5672
27499967 10 5672
29999964 11 5672
32499961 12 5672
34999958 13 5672
37499955 14 5672
39999952 15 5672
42499949 16 5...

output:


result:


Test #9:

score: 0
Runtime Error

input:

5000000 12499985000003
2499997 5 4321
4999994 4 4321
7499991 1 4321
9999988 2 4321
12499985 3 4321
14999982 10 4321
17499979 9 4321
19999976 8 4321
22499973 7 4321
24999970 6 4321
27499967 15 4321
29999964 14 4321
32499961 11 4321
34999958 12 4321
37499955 13 4321
39999952 16 4321
42499949 17 4321
4...

output:


result:


Test #10:

score: 0
Runtime Error

input:

5000000 12499985000004
2499997 5 4321
4999994 1 4322
7499991 4 4322
9999988 3 4321
12499985 2 4322
14999982 6 4321
17499979 7 4322
19999976 8 4322
22499973 10 4322
24999970 9 4321
27499967 11 4323
29999964 12 4323
32499961 13 4322
34999958 15 4323
37499955 14 4322
39999952 20 4323
42499949 18 4321
4...

output:


result: