Submission #25309

#	Time	Username	Problem	Language	Result	Execution time	Memory
25309		kdh9949	Pinball (JOI14_pinball)	C++14	100 / 100	319 ms	21136 KiB

pinball

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

const ll inf = 1e18;
int n, m, s[100010], e[100010], x[100010], c[100010], xx[300010];
ll ans = inf;

int cp(int x){ return (int)(lower_bound(xx + 1, xx + 3 * m + 3, x) - xx); }

const int sz = 524288;
struct Seg{
	ll dat[2 * sz];
	void ini(){ fill(dat + 1, dat + 2 * sz, inf); }
	void upd(int x, ll v){
		x += sz - 1; dat[x] = min(dat[x], v);
		for(x /= 2; x; x /= 2) dat[x] = min(dat[2 * x], dat[2 * x + 1]);
	}
	ll get(int s, int e){
		ll ret = inf;
		for(s += sz - 1, e += sz - 1; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) ret = min(ret, dat[s++]);
			if(e % 2 == 0) ret = min(ret, dat[e--]);
		}
		return ret;
	}
} LS, RS;

int main(){
	scanf("%d%d", &m, &n);
	for(int i = 0; i < m; i++){
		scanf("%d%d%d%d", s + i, e + i, x + i, c + i);
		xx[3 * i + 1] = s[i];
		xx[3 * i + 2] = e[i];
		xx[3 * i + 3] = x[i];
	}
	xx[3 * m + 1] = 1;
	xx[3 * m + 2] = n;
	sort(xx + 1, xx + 3 * m + 3);
	LS.ini(); RS.ini();
	LS.upd(cp(1), 0); RS.upd(cp(n), 0);
	for(int i = 0; i < m; i++){
		s[i] = cp(s[i]); e[i] = cp(e[i]); x[i] = cp(x[i]);
		ll lv = LS.get(s[i], e[i]), rv = RS.get(s[i], e[i]);
		ans = min(ans, lv + rv + c[i]);
		LS.upd(x[i], lv + c[i]);
		RS.upd(x[i], rv + c[i]);
	}
	printf("%lld\n", ans > (inf / 10 * 9) ? -1 : ans);
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:30:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &m, &n);
                       ^
pinball.cpp:32:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", s + i, e + i, x + i, c + i);
                                                ^

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