Submission #39734

#	Time	Username	Problem	Language	Result	Execution time	Memory
39734		14kg	Pinball (JOI14_pinball)	C++11	100 / 100	771 ms	48804 KiB

pinball

#include <stdio.h>
#include <map>
#include <set>
#include <algorithm>
#define N 100001
#define max2(x,y) (x>y?x:y)
#define INF 999999999999999999

using namespace std;
int n, m, M_len, nn;
long long tree[2][1048576];
pair<pair<int, int>, pair<int, int> > in[N], s_in[N];
set<int> S;
map<int, int> M;

long long min2(long long x, long long y) { return x < y ? x : y; }
pair<int, int> input() {
	int x, y;
	scanf("%d %d", &x, &y);
	return{ x,y };
}
long long get_seg(int lev, int l, int r, int x, int y, int tree_num) {
	int mid = (l + r) / 2;
	if (r < x || y < l) return INF;
	if (x <= l && r <= y) return tree[tree_num][lev];
	return min2(get_seg(lev * 2, l, mid, x, y, tree_num), get_seg(lev * 2 + 1, mid + 1, r, x, y, tree_num));
}
void Update(int x, int y) {
	tree[x][y] = min2(tree[x][y * 2], tree[x][y * 2 + 1]);
	if (y > 1) Update(x, y / 2);
}
void Push(int tree_num, int x, long long num) {
	tree[tree_num][nn + x - 1] = min2(tree[tree_num][nn + x - 1], num);
	Update(tree_num, (nn + x - 1) / 2);
}
int main() {
	int k = 1;
	long long out = INF;

	scanf("%d %d", &m, &n);
	for (int i = 1; i <= m; i++) {
		in[i].first = input(), in[i].second = input();
		s_in[i] = in[i];
	}
	sort(s_in + 1, s_in + m + 1);

	for (int i = 1; i <= m; i++)
		if (k < s_in[i].first.first) { printf("-1"); return 0; }
		else {
			k = max2(k, s_in[i].first.second + 1);
			S.insert(s_in[i].first.first), S.insert(s_in[i].first.second);
			S.insert(s_in[i].second.first);
		}
	if (k <= n) { printf("-1"); return 0; }
	for (auto i : S) M[i] = ++M_len;
	for (nn = 1; nn < M_len; nn *= 2);
	for (int i = 1; i < nn * 2; i++) tree[0][i] = tree[1][i] = INF;

	for (int i = 1; i <= m; i++) {
		int l = M[in[i].first.first];
		int r = M[in[i].first.second];
		int mid = M[in[i].second.first];

		long long SL = get_seg(1, 1, nn, l, r, 0);
		long long SR = get_seg(1, 1, nn, l, r, 1);
		if (l == 1) SL = 0;
		if (r == M_len) SR = 0;

		Push(0, mid, SL + (long long)in[i].second.second);
		Push(1, mid, SR + (long long)in[i].second.second);
		out = min2(out, SL + SR + (long long)in[i].second.second);
	} printf("%lld", out == INF ? -1 : out);
}

Compilation message (stderr)

pinball.cpp: In function 'std::pair<int, int> input()':
pinball.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &x, &y);
                        ^
pinball.cpp: In function 'int main()':
pinball.cpp:40:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &m, &n);
                        ^

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