oj.uz

답안 #200821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200821 2020-02-08T09:09:04 Z maruii Long Distance Coach (JOI17_coach) C++14
16 / 100
 75 ms 117880 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define ff first
#define ss second

int N, M;
struct CHT {
	struct Node {
		pii L;
		int l, r;
		Node() : L(pii(0, 1e18)), l(-1), r(-1) {}
	} A[5000005];
	ll f(pii L, int x) { return L.ff * x + L.ss; }
	int cnt;
	void update(int nn, int s, int e, pii L2) {
		pii &L1 = A[nn].L;
		if (f(L1, s) > f(L2, s)) swap(L1, L2);
		if (f(L1, e) <= f(L2, e)) return;
		int m = s + e >> 1;
		if (f(L1, m) > f(L2, m)) {
			if (A[nn].l < 0) A[nn].l = ++cnt;
			update(A[nn].l, s, m, L2);
		}
		else {
			if (A[nn].r < 0) A[nn].r = ++cnt;
			update(A[nn].r, m + 1, e, L2);
		}
	}
	void update(ll a, ll b) { update(0, 0, M, pii(a, b)); }
	ll query(int nn, int s, int e, int x) {
		if (nn < 0 || s > x || e < x) return 1e18;
		ll ret = f(A[nn].L, x);
		int m = s + e >> 1;
		return min({ret, query(A[nn].l, s, m, x), query(A[nn].r, m + 1, e, x)});
	}
	ll query(int x) { return query(0, 0, M, x); }
} cht;
ll X, T, W;
pii R[200005], P[200005];
ll D[200005], H[200005], S[200005];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> X >> N >> M >> W >> T;
	for (int i = 0; i < N; ++i) {
		ll x; cin >> x;
		R[i] = {x % T, x / T};
	}
	for (int i = 1; i <= M; ++i) cin >> P[i].ff >> P[i].ss;
	R[N] = {X % T, X / T};
	sort(R, R + N + 1);
	sort(P + 1, P + M + 1);
	for (int i = 1; i <= M; ++i) {
		S[i] = S[i - 1] + P[i].ss;
		H[i] = X / T + (X % T >= P[i].ff);
	}
	H[0] = X / T + 1;
	for (int i = M, j = N; i; --i) {
		while (j >= 0 && R[j].ff > P[i].ff) {
			cht.update(-W * R[j].ss, D[i + 1] + S[i] + W * i * R[j].ss);
			--j;
		}
		D[i] = min(cht.query(i - 1) - S[i - 1], D[i + 1] + H[i] * W);
	}
	cout << D[1] + H[0] * W;
	return 0;
}

Compilation message

coach.cpp: In member function 'void CHT::update(int, int, int, pii)':
coach.cpp:21:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~
coach.cpp: In member function 'll CHT::query(int, int, int, int)':
coach.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 117752 KB Output is correct
2 Correct 69 ms 117752 KB Output is correct
3 Correct 70 ms 117752 KB Output is correct
4 Correct 69 ms 117752 KB Output is correct
5 Correct 70 ms 117752 KB Output is correct
6 Correct 68 ms 117744 KB Output is correct
7 Correct 70 ms 117880 KB Output is correct
8 Correct 73 ms 117880 KB Output is correct
9 Correct 67 ms 117752 KB Output is correct
10 Correct 70 ms 117756 KB Output is correct
11 Correct 70 ms 117752 KB Output is correct
12 Correct 69 ms 117752 KB Output is correct
13 Correct 68 ms 117752 KB Output is correct
14 Correct 68 ms 117752 KB Output is correct
15 Correct 67 ms 117752 KB Output is correct
16 Correct 70 ms 117772 KB Output is correct
17 Correct 68 ms 117752 KB Output is correct
18 Correct 69 ms 117752 KB Output is correct
19 Correct 68 ms 117752 KB Output is correct
20 Correct 75 ms 117756 KB Output is correct
21 Correct 68 ms 117752 KB Output is correct
22 Correct 69 ms 117752 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 117752 KB Output is correct
2 Correct 69 ms 117752 KB Output is correct
3 Correct 70 ms 117752 KB Output is correct
4 Correct 69 ms 117752 KB Output is correct
5 Correct 70 ms 117752 KB Output is correct
6 Correct 68 ms 117744 KB Output is correct
7 Correct 70 ms 117880 KB Output is correct
8 Correct 73 ms 117880 KB Output is correct
9 Correct 67 ms 117752 KB Output is correct
10 Correct 70 ms 117756 KB Output is correct
11 Correct 70 ms 117752 KB Output is correct
12 Correct 69 ms 117752 KB Output is correct
13 Correct 68 ms 117752 KB Output is correct
14 Correct 68 ms 117752 KB Output is correct
15 Correct 67 ms 117752 KB Output is correct
16 Correct 70 ms 117772 KB Output is correct
17 Correct 68 ms 117752 KB Output is correct
18 Correct 69 ms 117752 KB Output is correct
19 Correct 68 ms 117752 KB Output is correct
20 Correct 75 ms 117756 KB Output is correct
21 Correct 68 ms 117752 KB Output is correct
22 Correct 69 ms 117752 KB Output is correct
23 Incorrect 71 ms 117880 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 117752 KB Output is correct
2 Correct 69 ms 117752 KB Output is correct
3 Correct 70 ms 117752 KB Output is correct
4 Correct 69 ms 117752 KB Output is correct
5 Correct 70 ms 117752 KB Output is correct
6 Correct 68 ms 117744 KB Output is correct
7 Correct 70 ms 117880 KB Output is correct
8 Correct 73 ms 117880 KB Output is correct
9 Correct 67 ms 117752 KB Output is correct
10 Correct 70 ms 117756 KB Output is correct
11 Correct 70 ms 117752 KB Output is correct
12 Correct 69 ms 117752 KB Output is correct
13 Correct 68 ms 117752 KB Output is correct
14 Correct 68 ms 117752 KB Output is correct
15 Correct 67 ms 117752 KB Output is correct
16 Correct 70 ms 117772 KB Output is correct
17 Correct 68 ms 117752 KB Output is correct
18 Correct 69 ms 117752 KB Output is correct
19 Correct 68 ms 117752 KB Output is correct
20 Correct 75 ms 117756 KB Output is correct
21 Correct 68 ms 117752 KB Output is correct
22 Correct 69 ms 117752 KB Output is correct
23 Incorrect 71 ms 117880 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 117752 KB Output is correct
2 Correct 69 ms 117752 KB Output is correct
3 Correct 70 ms 117752 KB Output is correct
4 Correct 69 ms 117752 KB Output is correct
5 Correct 70 ms 117752 KB Output is correct
6 Correct 68 ms 117744 KB Output is correct
7 Correct 70 ms 117880 KB Output is correct
8 Correct 73 ms 117880 KB Output is correct
9 Correct 67 ms 117752 KB Output is correct
10 Correct 70 ms 117756 KB Output is correct
11 Correct 70 ms 117752 KB Output is correct
12 Correct 69 ms 117752 KB Output is correct
13 Correct 68 ms 117752 KB Output is correct
14 Correct 68 ms 117752 KB Output is correct
15 Correct 67 ms 117752 KB Output is correct
16 Correct 70 ms 117772 KB Output is correct
17 Correct 68 ms 117752 KB Output is correct
18 Correct 69 ms 117752 KB Output is correct
19 Correct 68 ms 117752 KB Output is correct
20 Correct 75 ms 117756 KB Output is correct
21 Correct 68 ms 117752 KB Output is correct
22 Correct 69 ms 117752 KB Output is correct
23 Incorrect 71 ms 117880 KB Output isn't correct
24 Halted 0 ms 0 KB -