Submission #56553

#	Time	Username	Problem	Language	Result	Execution time	Memory
56553		Bruteforceman	Pinball (JOI14_pinball)	C++11	51 / 100	1053 ms	22240 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
int M, N;
int a[100010], b[100010], c[100010];
int cost[100010];
long long pre[100010];
long long suf[100010];
const long long inf = 1e18;
long long t[500010 * 4];
int idx;

long long query(int x, int y, int c = 1, int b = 1, int e = idx) {
	if(x <= b && e <= y) {
		return t[c];
	}
	if(y < b || e < x) return inf;
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	return min(query(x, y, l, b, m), query(x, y, r, m+1, e));
}
void update(int x, long long val, int c = 1, int b = 1, int e = idx) {
	if(b == e) {
		t[c] = min(t[c], val);
		return ;
	} 
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) update(x, val, l, b, m); 
	else update(x, val, r, m+1, e);
	t[c] = min(t[l], t[r]);
}

int main(int argc, char const *argv[])
{
	map <int, int> com;
	scanf("%d %d", &M, &N);

	com[1]; com[N];
	for(int i = 1; i <= M; i++) {
		scanf("%d %d %d %d", &a[i], &b[i], &c[i], &cost[i]);
		if(a[i] > 1) com[a[i] - 1];
		com[a[i]];
		if(b[i] < N) com[b[i] + 1];
		com[b[i]];
		com[c[i]];
	}
	idx = 0;
	for(auto &i : com) {
		i.second = ++idx;
	}
	for(int i = 1; i <= M; i++) {
		a[i] = com[a[i]];
		b[i] = com[b[i]];
		c[i] = com[c[i]];
	}
	int start = com[1];
	int end = com[N];
	for(int i = 0; i <= 4 * idx; i++) {
		t[i] = inf;
	}
	for(int i = 1; i <= M; i++) {
		if(a[i] == start) {
			pre[i] = cost[i];
		} else {
			pre[i] = inf;
		}
		pre[i] = min(pre[i], query(a[i], b[i]) + cost[i]);
		update(c[i], pre[i]);
	}
	for(int i = 0; i <= 4 * idx; i++) {
		t[i] = inf;
	}
	for(int i = 1; i <= M; i++) {
		if(b[i] == end) {
			suf[i] = cost[i];
		} else {
			suf[i] = inf;
		}
		suf[i] = min(suf[i], query(a[i], b[i]) + cost[i]);
		update(c[i], suf[i]);
	}
	long long ans = inf;
	for(int i = 1; i <= M; i++) {
		ans = min(ans, pre[i] + suf[i] - cost[i]);
	}
	if(ans > (inf / 3)) {
		ans = -1;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main(int, const char**)':
pinball.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &M, &N);
  ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &a[i], &b[i], &c[i], &cost[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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