답안 #52589 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52589	2018-06-26T08:07:59 Z	baactree	Pinball (JOI14_pinball)	C++17	100 / 100	285 ms	23028 KB

pinball

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m, n;
int A[100005], B[100005], C[100005], D[100005];
ll inf = 0x3f3f3f3f3f3f3f3f;
vector<int> xidx;
int sz;
struct SGT {
	ll tree[300005 << 2];
	SGT() {
		memset(tree, 0x3f, sizeof(tree));
	}
	void update(int idx, ll val) {
		idx += sz;
		while (idx) {
            tree[idx]=min(tree[idx],val);
            idx/=2;
		}
	}
	ll query(int le, int ri) {
		le += sz;
		ri += sz;
		ll ret = inf;
		while (le <= ri) {
			if (le & 1)ret = min(ret, tree[le++]);
			if (!(ri & 1))ret = min(ret, tree[ri--]);
			le /= 2;
			ri /= 2;
		}
		return ret;
	}
};
int get_idx(int x) {
	return lower_bound(xidx.begin(), xidx.end(), x) - xidx.begin();
}
SGT lsgt, rsgt;
int main() {
	scanf("%d%d", &m, &n);
	xidx.push_back(1);
	xidx.push_back(n);
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
		xidx.push_back(A[i]);
		xidx.push_back(B[i]);
		xidx.push_back(C[i]);
	}
	sort(xidx.begin(), xidx.end());
	xidx.erase(unique(xidx.begin(), xidx.end()), xidx.end());
	sz = 1;
	while (sz < xidx.size())sz *= 2;
	lsgt.update(0, 0);
	rsgt.update(xidx.size() - 1, 0);
	ll ans = inf;
	for (int i = 0; i < m; i++) {
		ll le = lsgt.query(get_idx(A[i]), get_idx(B[i]));
		lsgt.update(get_idx(C[i]), le+D[i]);
		ll ri = rsgt.query(get_idx(A[i]), get_idx(B[i]));
		rsgt.update(get_idx(C[i]), ri+D[i]);
		ans = min(ans, min(le + ri, inf) + D[i]);
	}
	printf("%lld\n", ans == inf ? -1 : ans);
	return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:51:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (sz < xidx.size())sz *= 2;
         ~~~^~~~~~~~~~~~~
pinball.cpp:39: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:43: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], &D[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	19064 KB	Output is correct
2	Correct	18 ms	19300 KB	Output is correct
3	Correct	18 ms	19300 KB	Output is correct
4	Correct	16 ms	19416 KB	Output is correct
5	Correct	19 ms	19416 KB	Output is correct
6	Correct	15 ms	19416 KB	Output is correct
7	Correct	16 ms	19416 KB	Output is correct
8	Correct	21 ms	19416 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	19064 KB	Output is correct
2	Correct	18 ms	19300 KB	Output is correct
3	Correct	18 ms	19300 KB	Output is correct
4	Correct	16 ms	19416 KB	Output is correct
5	Correct	19 ms	19416 KB	Output is correct
6	Correct	15 ms	19416 KB	Output is correct
7	Correct	16 ms	19416 KB	Output is correct
8	Correct	21 ms	19416 KB	Output is correct
9	Correct	17 ms	19416 KB	Output is correct
10	Correct	16 ms	19416 KB	Output is correct
11	Correct	16 ms	19416 KB	Output is correct
12	Correct	16 ms	19436 KB	Output is correct
13	Correct	18 ms	19436 KB	Output is correct
14	Correct	16 ms	19436 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	19064 KB	Output is correct
2	Correct	18 ms	19300 KB	Output is correct
3	Correct	18 ms	19300 KB	Output is correct
4	Correct	16 ms	19416 KB	Output is correct
5	Correct	19 ms	19416 KB	Output is correct
6	Correct	15 ms	19416 KB	Output is correct
7	Correct	16 ms	19416 KB	Output is correct
8	Correct	21 ms	19416 KB	Output is correct
9	Correct	17 ms	19416 KB	Output is correct
10	Correct	16 ms	19416 KB	Output is correct
11	Correct	16 ms	19416 KB	Output is correct
12	Correct	16 ms	19436 KB	Output is correct
13	Correct	18 ms	19436 KB	Output is correct
14	Correct	16 ms	19436 KB	Output is correct
15	Correct	16 ms	19436 KB	Output is correct
16	Correct	16 ms	19436 KB	Output is correct
17	Correct	18 ms	19452 KB	Output is correct
18	Correct	20 ms	19452 KB	Output is correct
19	Correct	17 ms	19452 KB	Output is correct
20	Correct	17 ms	19452 KB	Output is correct
21	Correct	17 ms	19452 KB	Output is correct
22	Correct	18 ms	19452 KB	Output is correct
23	Correct	18 ms	19580 KB	Output is correct
24	Correct	17 ms	19580 KB	Output is correct

Subtask #4
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	19064 KB	Output is correct
2	Correct	18 ms	19300 KB	Output is correct
3	Correct	18 ms	19300 KB	Output is correct
4	Correct	16 ms	19416 KB	Output is correct
5	Correct	19 ms	19416 KB	Output is correct
6	Correct	15 ms	19416 KB	Output is correct
7	Correct	16 ms	19416 KB	Output is correct
8	Correct	21 ms	19416 KB	Output is correct
9	Correct	17 ms	19416 KB	Output is correct
10	Correct	16 ms	19416 KB	Output is correct
11	Correct	16 ms	19416 KB	Output is correct
12	Correct	16 ms	19436 KB	Output is correct
13	Correct	18 ms	19436 KB	Output is correct
14	Correct	16 ms	19436 KB	Output is correct
15	Correct	16 ms	19436 KB	Output is correct
16	Correct	16 ms	19436 KB	Output is correct
17	Correct	18 ms	19452 KB	Output is correct
18	Correct	20 ms	19452 KB	Output is correct
19	Correct	17 ms	19452 KB	Output is correct
20	Correct	17 ms	19452 KB	Output is correct
21	Correct	17 ms	19452 KB	Output is correct
22	Correct	18 ms	19452 KB	Output is correct
23	Correct	18 ms	19580 KB	Output is correct
24	Correct	17 ms	19580 KB	Output is correct
25	Correct	34 ms	19836 KB	Output is correct
26	Correct	72 ms	20344 KB	Output is correct
27	Correct	177 ms	21372 KB	Output is correct
28	Correct	167 ms	22892 KB	Output is correct
29	Correct	129 ms	22892 KB	Output is correct
30	Correct	201 ms	22896 KB	Output is correct
31	Correct	265 ms	23024 KB	Output is correct
32	Correct	256 ms	23024 KB	Output is correct
33	Correct	45 ms	23024 KB	Output is correct
34	Correct	129 ms	23024 KB	Output is correct
35	Correct	174 ms	23024 KB	Output is correct
36	Correct	285 ms	23028 KB	Output is correct
37	Correct	245 ms	23028 KB	Output is correct
38	Correct	263 ms	23028 KB	Output is correct

답안 #52589

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 18.0 / 18.0

Subtask #3 22.0 / 22.0

Subtask #4 49.0 / 49.0

Subtask #1
11.0 / 11.0

Subtask #2
18.0 / 18.0

Subtask #3
22.0 / 22.0

Subtask #4
49.0 / 49.0