oj.uz

Submission #39733

# Submission time Handle Problem Language Result Execution time Memory
39733 2018-01-18T02:44:33 Z 14kg Pinball (JOI14_pinball) C++11
18 / 100
 359 ms 30192 KB 
#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] = 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

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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 20688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 20688 KB Output is correct
2 Correct 0 ms 20688 KB Output is correct
3 Correct 0 ms 20688 KB Output is correct
4 Correct 0 ms 20820 KB Output is correct
5 Correct 1 ms 20820 KB Output is correct
6 Correct 0 ms 20820 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 20688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 22272 KB Output is correct
2 Correct 129 ms 25968 KB Output is correct
3 Correct 359 ms 30192 KB Output is correct
4 Incorrect 174 ms 20820 KB Output isn't correct
5 Halted 0 ms 0 KB -