Submission #284186

#	Time	Username	Problem	Language	Result	Execution time	Memory
284186		ChrisT	Pinball (JOI14_pinball)	C++17	100 / 100	210 ms	12556 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
vector<int> xs;
int getx (int x) {return lower_bound(xs.begin(),xs.end(),x) - xs.begin() + 1;}
const int MN = 3e5 + 5; const long long INF = 1e18;
long long tree[MN<<1]; int sz;
void update (int i, long long v) {
	if (v >= tree[i += sz - 1]) return;
	for (tree[i] = v; i > 1; i >>= 1) 
		tree[i>>1] = min(tree[i],tree[i^1]);
}
long long query (int l, int r) {
	long long res = INF;
	for (l+=sz-1,r+=sz;l<r;l>>=1,r>>=1) {
		if (l&1) res = min(res,tree[l++]);
		if (r&1) res = min(res,tree[--r]);
	} 
	return res;
}
int main () {
	int m,n;
	scanf ("%d %d",&m,&n);
	vector<array<int,4>> v(m);
	for (auto &au : v) {
		scanf ("%d %d %d %d",&au[0],&au[1],&au[2],&au[3]);
		xs.push_back(au[0]); xs.push_back(au[1]); xs.push_back(au[2]);
	}
	xs.push_back(1); xs.push_back(n);
	sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
	sz = xs.size();
	long long ans = INF; vector<long long> mn(m);
	for (int i = 1; i < (sz << 1); i++) tree[i] = INF;
	update(getx(1),0);
	for (int i = 0; i < m; i++) {
		v[i][0] = getx(v[i][0]); v[i][1] = getx(v[i][1]); v[i][2] = getx(v[i][2]);
		mn[i] = query(v[i][0],v[i][1]);
		update(v[i][2],mn[i] + v[i][3]);
	}
	for (int i = 1; i < (sz << 1); i++) tree[i] = INF;
	update(getx(n),0);
	for (int i = 0; i < m; i++) {
		long long go = query(v[i][0],v[i][1]) + v[i][3];
		ans = min(ans,go + mn[i]);
		update(v[i][2],go);
	}
	if (ans >= INF/2) ans = -1;
	printf ("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf ("%d %d",&m,&n);
      |  ~~~~~~^~~~~~~~~~~~~~~
pinball.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf ("%d %d %d %d",&au[0],&au[1],&au[2],&au[3]);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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