oj.uz

Submission #39734

# Submission time Handle Problem Language Result Execution time Memory
39734 2018-01-18T02:51:17 Z 14kg Pinball (JOI14_pinball) C++11
100 / 100
 771 ms 48804 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] = 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

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.0 / 11.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 20688 KB Output is correct
5 Correct 0 ms 20688 KB Output is correct
6 Correct 0 ms 20688 KB Output is correct
7 Correct 0 ms 20688 KB Output is correct
8 Correct 0 ms 20688 KB Output is correct

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 1 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 1 ms 20820 KB Output is correct

Subtask #3
22.0 / 22.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 3 ms 20820 KB Output is correct
4 Correct 0 ms 20688 KB Output is correct
5 Correct 1 ms 20688 KB Output is correct
6 Correct 2 ms 20820 KB Output is correct
7 Correct 2 ms 20820 KB Output is correct
8 Correct 3 ms 20952 KB Output is correct
9 Correct 3 ms 20952 KB Output is correct
10 Correct 3 ms 20952 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 22272 KB Output is correct
2 Correct 118 ms 25968 KB Output is correct
3 Correct 369 ms 30192 KB Output is correct
4 Correct 170 ms 20820 KB Output is correct
5 Correct 251 ms 29268 KB Output is correct
6 Correct 293 ms 22404 KB Output is correct
7 Correct 648 ms 36396 KB Output is correct
8 Correct 574 ms 32040 KB Output is correct
9 Correct 74 ms 26232 KB Output is correct
10 Correct 298 ms 34812 KB Output is correct
11 Correct 406 ms 48804 KB Output is correct
12 Correct 771 ms 48804 KB Output is correct
13 Correct 692 ms 48804 KB Output is correct
14 Correct 615 ms 48804 KB Output is correct