Submission #52544

#	Time	Username	Problem	Language	Result	Execution time	Memory
52544		kriii	Pinball (JOI14_pinball)	C++17	100 / 100	276 ms	19888 KiB

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 (stderr)

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 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49