oj.uz

답안 #103049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103049 2019-03-28T22:43:16 Z luciocf Pinball (JOI14_pinball) C++14
0 / 100
 11 ms 9728 KB 
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

int ind;
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;

	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]];
}

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, m;
	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);
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:66: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:70: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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -