제출 #103050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103050		luciocf	Pinball (JOI14_pinball)	C++14	100 / 100	703 ms	30968 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5+10;
const long long inf = 2e18+10;

typedef long long ll;

int ind, m;
int l[maxn], r[maxn], p[maxn], d[maxn];

ll tree[4*maxn];

ll dp[2][maxn];

map<int, int> mp;

void compress(int n)
{
	for (int i = 1; i <= n; i++)
		mp[l[i]] = mp[r[i]] = mp[p[i]] = 0;

	mp[1] = 0;
	mp[m] = 0;

	for (auto &x: mp)
		x.second = ++ind;

	for (int i = 1; i <= n; i++)
		l[i] = mp[l[i]], r[i] = mp[r[i]], p[i] = mp[p[i]];

	m = mp[m];
}

void init(void)
{
	for (int i = 0; i < 4*maxn; i++)
		tree[i] = inf;
}

void upd(int node, int l, int r, int pos, ll v)
{
	if (l == r)
	{
		tree[node] = min(tree[node], v);
		return;
	}

	int mid = (l+r)>>1;

	if (pos <= mid) upd(2*node, l, mid, pos, v);
	else upd(2*node+1, mid+1, r, pos, v);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

ll query(int node, int l, int r, int a, int b)
{
	if (l > b || r < a) return inf;
	if (l >= a && r <= b) return tree[node];

	int mid = (l+r)>>1;

	return min(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b));
}

int main(void)
{
	int n;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d %d %d", &l[i], &r[i], &p[i], &d[i]);

		dp[0][i] = dp[1][i] = inf;
	}

	compress(n);
	init();

	for (int i = 1; i <= n; i++)
	{
		if (l[i] == 1) dp[0][i] = d[i];
		else dp[0][i] = 1ll*d[i] + query(1, 1, ind, l[i], r[i]);

		upd(1, 1, ind, p[i], dp[0][i]);
	}

	init();

	for (int i = 1; i <= n; i++)
	{
		if (r[i] == m) dp[1][i] = d[i];
		else dp[1][i] = 1ll*d[i] + query(1, 1, ind, l[i], r[i]);

		upd(1, 1, ind, p[i], dp[1][i]);
	}

	ll ans = inf;
	for (int i = 1; i <= n; i++)
		if (dp[0][i] < inf && dp[1][i] < inf)
			ans = min(ans, dp[0][i]+dp[1][i]-1ll*d[i]);

	if (ans == inf) printf("-1\n");
	else printf("%lld\n", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

pinball.cpp: In function 'int main()':
pinball.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &l[i], &r[i], &p[i], &d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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