답안 #52544 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52544	2018-06-26T06:59:56 Z	kriii	Pinball (JOI14_pinball)	C++17	100 / 100	276 ms	19888 KB

pinball

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int N, M, a[101010], b[101010], c[101010], d[101010], e[404040];
 
const int Z = 1 << 19;
long long i1[Z * 2], i2[Z * 2];
 
void in(long long *a, int x, long long p)
{
	x += Z;
	while (x) {
		a[x] = min(a[x], p);
		x /= 2;
	}
}
 
const long long non = 1e18;
long long out(long long *a, int x, int y)
{
	long long r = non;
	x += Z; y += Z;
	while (x < y) {
		if (x & 1) r = min(r, a[x++]);
		if (~y & 1) r = min(r, a[y--]);
		x /= 2; y /= 2;
	} if (x == y) r = min(r, a[x]);
	return r;
}
 
int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) scanf("%d %d %d %d", a + i, b + i, c + i, d + i);
 
	int C = 0;
	e[C++] = 1;
	e[C++] = M;
	for (int i = 0; i < N; i++) {
		e[C++] = a[i];
		e[C++] = b[i];
		e[C++] = c[i];
	}
	sort(e, e + C);
	C = unique(e, e + C) - e;
	for (int i = 0; i < N; i++) {
		a[i] = lower_bound(e, e + C, a[i]) - e;
		b[i] = lower_bound(e, e + C, b[i]) - e;
		c[i] = lower_bound(e, e + C, c[i]) - e;
	}
 
	for (int i = 0; i < 2 * Z; i++) i1[i] = i2[i] = non;
	in(i1, 0, 0);
	in(i2, C - 1, 0);
	long long ans = non;
	for (int i = 0; i < N; i++) {
		long long o1 = out(i1, a[i], b[i]);
		in(i1, c[i], o1 + d[i]);
		long long o2 = out(i2, a[i], b[i]);
		in(i2, c[i], o2 + d[i]);
		ans = min(ans, o1 + o2 + d[i]);
	}
	if (ans == non) ans = -1;
	printf("%lld\n", ans);
 
	return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:35:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; i++) scanf("%d %d %d %d", a + i, b + i, c + i, d + i);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	16760 KB	Output is correct
2	Correct	14 ms	16768 KB	Output is correct
3	Correct	14 ms	16944 KB	Output is correct
4	Correct	15 ms	16944 KB	Output is correct
5	Correct	14 ms	16944 KB	Output is correct
6	Correct	13 ms	17028 KB	Output is correct
7	Correct	13 ms	17060 KB	Output is correct
8	Correct	13 ms	17060 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	16760 KB	Output is correct
2	Correct	14 ms	16768 KB	Output is correct
3	Correct	14 ms	16944 KB	Output is correct
4	Correct	15 ms	16944 KB	Output is correct
5	Correct	14 ms	16944 KB	Output is correct
6	Correct	13 ms	17028 KB	Output is correct
7	Correct	13 ms	17060 KB	Output is correct
8	Correct	13 ms	17060 KB	Output is correct
9	Correct	13 ms	17060 KB	Output is correct
10	Correct	14 ms	17060 KB	Output is correct
11	Correct	14 ms	17060 KB	Output is correct
12	Correct	15 ms	17060 KB	Output is correct
13	Correct	16 ms	17060 KB	Output is correct
14	Correct	15 ms	17088 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	16760 KB	Output is correct
2	Correct	14 ms	16768 KB	Output is correct
3	Correct	14 ms	16944 KB	Output is correct
4	Correct	15 ms	16944 KB	Output is correct
5	Correct	14 ms	16944 KB	Output is correct
6	Correct	13 ms	17028 KB	Output is correct
7	Correct	13 ms	17060 KB	Output is correct
8	Correct	13 ms	17060 KB	Output is correct
9	Correct	13 ms	17060 KB	Output is correct
10	Correct	14 ms	17060 KB	Output is correct
11	Correct	14 ms	17060 KB	Output is correct
12	Correct	15 ms	17060 KB	Output is correct
13	Correct	16 ms	17060 KB	Output is correct
14	Correct	15 ms	17088 KB	Output is correct
15	Correct	13 ms	17088 KB	Output is correct
16	Correct	14 ms	17088 KB	Output is correct
17	Correct	15 ms	17088 KB	Output is correct
18	Correct	15 ms	17088 KB	Output is correct
19	Correct	19 ms	17132 KB	Output is correct
20	Correct	14 ms	17132 KB	Output is correct
21	Correct	17 ms	17132 KB	Output is correct
22	Correct	16 ms	17132 KB	Output is correct
23	Correct	15 ms	17132 KB	Output is correct
24	Correct	15 ms	17132 KB	Output is correct

Subtask #4
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	16760 KB	Output is correct
2	Correct	14 ms	16768 KB	Output is correct
3	Correct	14 ms	16944 KB	Output is correct
4	Correct	15 ms	16944 KB	Output is correct
5	Correct	14 ms	16944 KB	Output is correct
6	Correct	13 ms	17028 KB	Output is correct
7	Correct	13 ms	17060 KB	Output is correct
8	Correct	13 ms	17060 KB	Output is correct
9	Correct	13 ms	17060 KB	Output is correct
10	Correct	14 ms	17060 KB	Output is correct
11	Correct	14 ms	17060 KB	Output is correct
12	Correct	15 ms	17060 KB	Output is correct
13	Correct	16 ms	17060 KB	Output is correct
14	Correct	15 ms	17088 KB	Output is correct
15	Correct	13 ms	17088 KB	Output is correct
16	Correct	14 ms	17088 KB	Output is correct
17	Correct	15 ms	17088 KB	Output is correct
18	Correct	15 ms	17088 KB	Output is correct
19	Correct	19 ms	17132 KB	Output is correct
20	Correct	14 ms	17132 KB	Output is correct
21	Correct	17 ms	17132 KB	Output is correct
22	Correct	16 ms	17132 KB	Output is correct
23	Correct	15 ms	17132 KB	Output is correct
24	Correct	15 ms	17132 KB	Output is correct
25	Correct	28 ms	17276 KB	Output is correct
26	Correct	57 ms	17700 KB	Output is correct
27	Correct	160 ms	18940 KB	Output is correct
28	Correct	147 ms	19804 KB	Output is correct
29	Correct	108 ms	19804 KB	Output is correct
30	Correct	171 ms	19804 KB	Output is correct
31	Correct	234 ms	19888 KB	Output is correct
32	Correct	217 ms	19888 KB	Output is correct
33	Correct	40 ms	19888 KB	Output is correct
34	Correct	106 ms	19888 KB	Output is correct
35	Correct	165 ms	19888 KB	Output is correct
36	Correct	276 ms	19888 KB	Output is correct
37	Correct	230 ms	19888 KB	Output is correct
38	Correct	236 ms	19888 KB	Output is correct

답안 #52544

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 18.0 / 18.0

Subtask #3 22.0 / 22.0

Subtask #4 49.0 / 49.0

Subtask #1
11.0 / 11.0

Subtask #2
18.0 / 18.0

Subtask #3
22.0 / 22.0

Subtask #4
49.0 / 49.0