Submission #952759

#	Time	Username	Problem	Language	Result	Execution time	Memory
952759		starchan	Pinball (JOI14_pinball)	C++17	100 / 100	187 ms	36800 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
struct segment_tree
{
	vector<int> tree;
	void init(int n)
	{
		tree.assign(4*n+69, INF);
		return;
	}
	void upd(int pos, int va, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id] = min(tree[id], va);
			return;
		}
		int m = (l+r)/2;
		if(pos <= m)
			upd(pos, va, 2*id, l, m);
		else
			upd(pos, va, 2*id+1, m+1, r);
		tree[id] = min(tree[2*id], tree[2*id+1]);
		return;
	}
	int val(int ql, int qr, int id, int l, int r)
	{
		if(r < ql || qr < l)
			return INF;
		if(ql <= l && r <= qr)
			return tree[id];
		int m = (l+r)/2;
		int s1 = val(ql, qr, 2*id, l, m);
		int s2 = val(ql, qr, 2*id+1, m+1, r);
		return min(s1, s2);
	}
};
vector<int> chungus;
int compress(int x)
{
	return lower_bound(chungus.begin(), chungus.end(), x) - chungus.begin();
}
signed main()
{
	fast();
	segment_tree work_l, work_r;
	int n, N;
	cin >> n >> N;
	work_l.init(3*n+1);
	work_r.init(3*n+1);
	vector<int> v;
	v.pb(1);
	v.pb(N);
	vector<int> a(n+1), b(n+1), c(n+1), d(n+1);
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		v.pb(a[i]);
		v.pb(b[i]);
		v.pb(c[i]);
	}
	chungus.pb(-INF);
	sort(v.begin(), v.end());
	for(auto x: v)
	{
		if(x!=chungus.back())
			chungus.pb(x);
	}
	for(int i = 1; i <= n; i++)
	{
		a[i] = compress(a[i]);
		b[i] = compress(b[i]);
		c[i] = compress(c[i]);
	}
	int L = compress(1);
	int R = compress(N);
	vector<int> dp_l, dp_r;
	dp_l.assign(n+1, INF);
	dp_r.assign(n+1, INF);	
	for(int i = 1; i <= n; i++)
	{
		if(a[i] == L)
			dp_l[i] = d[i];
		else
			dp_l[i] = d[i] + work_l.val(a[i], b[i], 1, L, R);
		dp_l[i] = min(dp_l[i], INF);
		work_l.upd(c[i], dp_l[i], 1, L, R);
	}
	for(int i = 1; i <= n; i++)
	{
		if(b[i] == R)
			dp_r[i] = d[i];
		else
			dp_r[i] = d[i] + work_r.val(a[i], b[i], 1, L, R);
		work_r.upd(c[i], dp_r[i], 1, L, R);
	}
	int ans = INF;
	for(int i = 1; i <= n; i++)
		ans = min(ans, dp_l[i]+dp_r[i]-d[i]);
	ans++; ans%=(INF+1); ans--;
	cout << ans << "\n";
	return 0;
}	

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