#include <stdio.h>
#define N 200002
#define M 200001
#define INF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long yy[N], aa[N]; int cc[N], n;
long long qq[M], rr[M]; int m;
long long l, t;
long long *vv;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (vv[ii[j]] == vv[i_])
j++;
else if (vv[ii[j]] < vv[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
long double cross(long long x1, long long y1, long long x2, long long y2) {
return (long double) x1 * y2 - (long double) x2 * y1;
}
long long dp[N], dq[N];
long double crossp(int i, int j, int k) {
return cross(j - i, dp[j] - dp[i], k - i, dp[k] - dp[i]);
}
long double crossq(int i, int j, int k) {
return cross(j - i, dq[j] - dq[i], k - i, dq[k] - dq[i]);
}
long long evalp(int i, long long x) {
return dp[i] + x * i;
}
long long evalq(int i, long long x) {
return dq[i] + x * i;
}
int main() {
static int hh[M], ii[N], qu1[N], qu2[N];
int cnt1, cnt2, w, g, h, i, j, lower, upper;
long long x, a, ans;
scanf("%lld%d%d%d%lld", &l, &m, &n, &w, &t), n += 2, m++;
for (h = 0; h + 1 < m; h++) {
scanf("%lld", &x);
qq[h] = x / t, rr[h] = x % t;
}
qq[m - 1] = l / t, rr[h] = l % t;
for (h = 0; h < m; h++)
hh[h] = h;
vv = rr, sort(hh, 0, m);
yy[0] = 0, cc[0] = 0;
for (i = 1; i < n; i++)
scanf("%lld%d", &yy[i], &cc[i]);
yy[n - 1] = t, cc[n - 1] = 0;
for (i = 0; i < n; i++)
ii[i] = i;
vv = yy, sort(ii, 0, n);
for (i = 0; i + 1 < n; i++)
aa[i] = qq[m - 1] + (rr[m - 1] >= yy[ii[i]] ? 1 : 0);
cnt1 = cnt2 = 0;
for (j = 0, h = 0; j < n; j++) {
if (j == 0)
dp[0] = aa[0] * w - cc[0], dq[0] = INF;
else {
a = INF;
while (h < m && rr[hh[h]] < yy[ii[j]])
a = min(a, qq[hh[h++]]);
if (a == INF)
dq[j] = min(dq[j - 1] + aa[j - 1] * w, dp[j - 1]);
else {
dq[j] = INF;
if (cnt1) {
lower = -1, upper = cnt1 - 1;
while (upper - lower > 1) {
g = (lower + upper) / 2;
if (evalp(qu1[g], -a * w) > evalp(qu1[g + 1], -a * w))
lower = g;
else
upper = g;
}
g = upper;
dq[j] = min(dq[j], evalp(qu1[g], -a * w) + a * w * (j - 1));
}
if (cnt2) {
lower = -1, upper = cnt2 - 1;
while (upper - lower > 1) {
g = (lower + upper) / 2;
if (evalq(qu2[g], -a * w) > evalq(qu2[g + 1], -a * w))
lower = g;
else
upper = g;
}
g = upper;
dq[j] = min(dq[j], evalq(qu2[g], -a * w) + a * w * j);
}
}
dp[j] = dq[j] + aa[j] * w - cc[ii[j]];
}
if (dp[0] != INF) {
while (cnt1 >= 2 && crossp(qu1[cnt1 - 2], qu1[cnt1 - 1], j) <= 0)
cnt1--;
qu1[cnt1++] = j;
}
if (dq[0] != INF) {
while (cnt2 >= 2 && crossq(qu2[cnt2 - 2], qu2[cnt2 - 1], j) <= 0)
cnt2--;
qu2[cnt2++] = j;
}
}
ans = dp[n - 1] - aa[n - 1] * w;
for (i = 0; i < n; i++)
ans += cc[i];
printf("%lld\n", ans);
return 0;
}
Compilation message
coach.c: In function 'main':
coach.c:67:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%lld%d%d%d%lld", &l, &m, &n, &w, &t), n += 2, m++;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.c:69:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%lld", &x);
| ^~~~~~~~~~~~~~~~~
coach.c:78:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%lld%d", &yy[i], &cc[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
