Submission #36014

#	Time	Username	Problem	Language	Result	Execution time	Memory
36014		YoLo	Pinball (JOI14_pinball)	C++14	100 / 100	409 ms	14680 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define endl '\n'
#define pi acos(-1)
#define pque priority_queue
#define N 1000000
#define lmax LONG_LONG_MAX
typedef pair < int, int > ii;
typedef vector < int > vi;
typedef vector < vi > vii;
int mod = 1000000007;
int n, m, lef[100009], rig[100009], a[100009], b[100009], c[100009], d[100009], f[100009], itl[400009], itr[400009], p[100009], ans = lmax;
void updl(int k, int l, int r, int pos, int val)
{
	if(r < pos || l > pos || r < l)
		return;
	if(r == pos && l == pos)
	{
		itl[k] = val;
		return;
	}
	int mid = (l + r) / 2;
	updl(k * 2, l, mid, pos, val);
	updl(k * 2 + 1, mid + 1, r, pos, val);
	itl[k] = min(itl[k * 2], itl[k * 2 + 1]);
}
int getl(int k, int l, int r, int L, int R)
{
	if(r < L || R < l || r < l)
		return 1e18;
	if(L <= l && r <= R)
		return itl[k];
	int mid = (l + r) / 2;
	return min(getl(k * 2, l, mid, L, R), getl(k * 2 + 1, mid + 1, r, L, R));
}
void updr(int k, int l, int r, int pos, int val)
{
	if(r < pos || l > pos || r < l)
		return;
	if(r == pos && l == pos)
	{
		itr[k] = val;
		return;
	}
	int mid = (l + r) / 2;
	updr(k * 2, l, mid, pos, val);
	updr(k * 2 + 1, mid + 1, r, pos, val);
	itr[k] = min(itr[k * 2], itr[k * 2 + 1]);
}
int getr(int k, int l, int r, int L, int R)
{
	if(r < L || R < l || r < l)
		return 1e18;
	if(L <= l && r <= R)
		return itr[k];
	int mid = (l + r) / 2;
	return min(getr(k * 2, l, mid, L, R), getr(k * 2 + 1, mid + 1, r, L, R));
}
bool cmp(int u, int v)
{
	return c[u] < c[v];
}
signed main()
{
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		cin >> a[i] >> b[i] >> c[i] >> d[i], f[i] = i;
	sort(f + 1, f + 1 + n, cmp);
	for(int i = 1; i <= n; i ++)
		p[f[i]] = i;
	for(int i = 1; i <= 400000; i ++)
		itl[i] = itr[i] = 1e18;
	for(int i = 1; i <= n; i ++)
	{
		int l = 1;
		int r = n;
		while(l < r)
		{
			int mid = (l + r) / 2;
			if(c[f[mid]] < a[i])
				l = mid + 1;
			else
				r = mid;
		}
		int ll = l;
		l = 1;
		r = n;
		while(l < r)
		{
			int mid = (l + r + 1) / 2;
			if(c[f[mid]] > b[i])
				r = mid - 1;
			else
				l = mid;
		}
		int rr = l;
		if(a[i] == 1)
			lef[i] = d[i];
		else
		{
			int tak = getl(1, 1, n, ll, rr);
			if(tak < 1e18)
				lef[i] = tak + d[i];
		}
		if(lef[i] > 0)
			updl(1, 1, n, p[i], lef[i]);
		if(b[i] == m)
			rig[i] = d[i];
		else
		{
			int tak = getr(1, 1, n, ll, rr);
			if(tak < 1e18)
				rig[i] = tak + d[i];
		}
		if(rig[i] > 0)
			updr(1, 1, n, p[i], rig[i]);
		if(rig[i] > 0 && lef[i] > 0)
			ans = min(ans, rig[i] + lef[i] - d[i]);
		//cout << i << ' ' << l << ' ' << r << ' ' << p[i] << ' ' << lef[i] << ' ' << rig[i] << endl;
	}
	if(ans < 1e16)
		cout << ans;
	else
		cout << -1;
}

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