Submission #25241

#	Time	Username	Problem	Language	Result	Execution time	Memory
25241		khsoo01	Pinball (JOI14_pinball)	C++11	100 / 100	296 ms	31724 KiB

pinball

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const ll inf = 1e18;

ll n, m;

vector<ll> cp;
vector<tuple<ll,ll,ll,ll> > a;

struct segtree {
	ll val[1234567], lim;
	void init () {
		for(lim=1; lim<=cp.size(); lim<<=1);
		for(ll i=2*lim; --i; ) val[i] = inf;
	}
	void upd (ll P, ll V) {
		P += lim;
		while(P) {
			val[P] = min(val[P], V);
			P >>= 1;
		}
	}
	ll get (ll S, ll E) {
		ll ret = inf;
		S += lim; E += lim;
		while(S<=E) {
			if(S%2==1) {ret = min(val[S], ret); S++;}
			if(E%2==0) {ret = min(val[E], ret); E--;}
			S >>= 1; E >>= 1;
		}
		return ret;
	}
} l, r;

ll cpr (ll X) {
	return lower_bound(cp.begin(), cp.end(), X) - cp.begin();
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) {
		ll A, B, C, D;
		scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
		a.pb(make_tuple(A,B,C,D));
		cp.pb(A); cp.pb(B); cp.pb(C);
	}
	cp.pb(1); cp.pb(m);

	sort(cp.begin(), cp.end());
	cp.erase(unique(cp.begin(), cp.end()), cp.end());

	l.init(); l.upd(0, 0);
	r.init(); r.upd(cp.size()-1, 0);

	ll ans = inf;
	for(auto &T : a) {
		ll A, B, C, D; tie(A, B, C, D) = T;
		A = cpr(A); B = cpr(B); C = cpr(C);
		ll X = l.get(A, B), Y = r.get(A, B);
		ans = min(ans, X + Y + D);
		l.upd(C, X+D); r.upd(C, Y+D);
	}
	printf("%lld\n", (ans == inf ? -1 : ans));
}

Compilation message (stderr)

pinball.cpp: In member function 'void segtree::init()':
pinball.cpp:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(lim=1; lim<=cp.size(); lim<<=1);
                 ^
pinball.cpp: In function 'int main()':
pinball.cpp:43:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
                         ^
pinball.cpp:46:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
                                        ^

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