Submission #52464

#	Time	Username	Problem	Language	Result	Execution time	Memory
52464		ics0503	Pinball (JOI14_pinball)	C++17	100 / 100	267 ms	22564 KiB

pinball

#include<stdio.h>
#include<algorithm>
using namespace std;
struct xy {long long a, b, c, d;}a[121212];
long long ALL[414141], an = 0;
long long F(long long x) { return (lower_bound(ALL, ALL + an, x) - ALL); }
long long tree[2][1212121], tn;
long long min(long long a, long long b) { if (a < b)return a; return b; }
void insert_g(long long tp, long long w, long long g) { for (long long i = tn + w; i > 0; i /= 2)tree[tp][i] = min(tree[tp][i], g); }
long long search_g(long long tp, long long ss, long long ee) {
	long long s = ss + tn, e = ee + tn;
	long long res = 1e18;
	while (s <= e) {
		if (s % 2 == 1)res = min(res, tree[tp][s++]);
		if (e % 2 == 0)res = min(res, tree[tp][e--]);
		s /= 2; e /= 2;
	}
	return res;
}
int main() {
	long long n, m; scanf("%lld%lld", &m, &n);
	long long i, j;
	for (i = 0; i < m; i++) {
		scanf("%lld%lld%lld%lld", &a[i].a, &a[i].b, &a[i].c, &a[i].d);
		ALL[an++] = a[i].a; ALL[an++] = a[i].b; ALL[an++] = a[i].c;
	}
	ALL[an++] = 1; ALL[an++] = n;
	sort(ALL, ALL + an);
	an = unique(ALL, ALL + an) - ALL;
	for (tn = 1; tn < an; tn *= 2);
	for (i = 0; i < m; i++) a[i] = { F(a[i].a), F(a[i].b), F(a[i].c), a[i].d };
	for (i = 0; i < tn * 2; i++)tree[0][i] = tree[1][i] = 1e18;
	long long ans = 1e18;
	for (i = 0; i < m; i++) {
		long long l = (a[i].a == 0 ? 0 : search_g(0, a[i].a, a[i].b))+a[i].d;
		long long r = (a[i].b == an-1 ? 0 : search_g(1, a[i].a, a[i].b))+a[i].d;
		ans = min(ans, l + r - a[i].d);
		insert_g(0, a[i].c, l);
		insert_g(1, a[i].c, r);
	}
	if (ans > 1e17)printf("-1");
	else printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:22:15: warning: unused variable 'j' [-Wunused-variable]
  long long i, j;
               ^
pinball.cpp:21:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long n, m; scanf("%lld%lld", &m, &n);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~
pinball.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &a[i].a, &a[i].b, &a[i].c, &a[i].d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49