#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// My bug list :
// integer overflow
// 0based, 1based forgotten
// index out of bound
// n, m, i, j typo
// some cases are missing
const int MAX_N = 200010, MAX_K = 18;
const ll inf = 2e18;
ll X, n, m, W, T;
ll s[MAX_N];
ll dp[MAX_N], sp[MAX_N], pfc[MAX_N];
pair<ll,ll> man[MAX_N];
int nxt[MAX_K][MAX_N];
ll jsum[MAX_K][MAX_N];
void init_cost() {
{
ll sum = 0;
for (int i = 0;i < m;++i) {
pfc[i] = sum += man[i].second;
}
}
debug(sp, sp+m);
vector<int> stk {0};
sp[0] = 0;
for (int i = 0;i < m;++i) {
while (stk.size()) {
int id = stk.back();
if (sp[i] >= sp[id]) break;
stk.pop_back();
}
nxt[0][i] = stk.back();
jsum[0][i] = W * (i-stk.back()) * sp[i];
stk.pb(i);
}
for (int d = 1;d < MAX_K;++d) {
for (int i = 0;i < m;++i) {
nxt[d][i] = nxt[d-1][ nxt[d-1][i] ];
jsum[d][i] = jsum[d-1][i] + jsum[d-1][ nxt[d-1][i] ];
}
}
}
ll pay(int l, int r) {
if (l > r) return 0;
ll ret = pfc[r] - (l?pfc[l-1]:0);
for (int d = MAX_K-1;d >= 0;--d) {
if (nxt[d][r] < l) continue;
ret += jsum[d][r];
r = nxt[d][r];
}
// assert(r >= l);
// assert(nxt[0][r] < l);
ret += sp[r] * (r-l+1) * W;
return ret;
}
ll cost(int l, int r) {
return dp[l] + pay(l+1, r-1);
}
// N refill points, and M people
// remember the driver need water too
ll F(pair<ll,ll> a, ll x) { return a.first * x + a.second; }
// floor ( y / x )
ll fdiv(ll a, ll b) {
assert( b >= 0 );
if (b == 0) return 0;
return a / b - (a < 0 && a % b);
}
ll inter(pair<ll,ll> a, pair<ll,ll> b) {
if (a < b) swap(a, b);
auto [m1, v1] = a;
auto [m2, v2] = b;
assert(m1 >= m2);
return fdiv(v2 - v1, m1 - m2);
}
pair<ll,ll> get_line(int ind) {
return make_pair(-ind, dp[ind] - pfc[ind]);
}
ll inter(ll a, ll b) { return inter(get_line(a), get_line(b)); }
ll F(ll a, ll x) { return F(get_line(a), x); }
// slope in deque is decreasing
//
//struct minconv {
// deque< pair<ll,ll> > dq;
// // put a line, and the line has the maximum slope
// void pb(pair<ll,ll> line) {
// //if (false)
// while (dq.size() > 1) {
// auto a = dq[0], b = dq[1];
// if (inter(line, a) < inter(a, b)) break;
// dq.pop_front();
// }
// dq.push_front(line);
// }
// // put a line, and the line has the minimum slope
// void pf(pair<ll,ll> line) {
// //if (false)
// while (dq.size() > 1) {
// auto a = end(dq)[-2], b = end(dq)[-1];
// if (inter(a, b) < inter(b, line)) break;
// dq.pop_back();
// }
// dq.push_back(line);
// }
// pair<ll,ll> pop_back() { auto ret = dq.back(); dq.pop_back(); return ret; }
// pair<ll,ll> pop_front() { auto ret = dq.front(); dq.pop_front(); return ret; }
// int qq(int i) {
// ll v = inf, ret = 0;
// for (int j = 0;j < dq.size();++j)
// if (chmin(v, cost(dq[j].first, i)))
// ret = dq[j].first;
// return ret;
// }
// int qrypoint(ll x) {
// if (dq.empty()) return 0;
//
// int l = 0, r = (int) dq.size() - 1, mid;
// while (l < r) {
// mid = l + r >> 1;
// if (F(dq[mid], x) <= F(dq[mid+1], x))
// r = mid;
// else
// l = mid+1;
// }
// return dq[l].first;
// }
// void clear() {
// deque<pair<ll,ll>>().swap(dq);
// }
//};
//
//struct minconv {
// deque< ll > dq;
// // put a line, and the line has the miminum slope
// void pb(ll line) {
// while (dq.size() > 1) {
// auto a = end(dq)[-2], b = end(dq)[-1];
// if (inter(a, b) < inter(b, line)) break;
// dq.pop_back();
// }
// dq.push_back(line);
// }
// // put a line, and the line has the maximum slope
// void pf(ll line) {
// while (dq.size() > 1) {
// auto a = dq[0], b = dq[1];
// if (inter(line, a) < inter(a, b)) break;
// dq.pop_front();
// }
// dq.push_front(line);
// }
// ll pop_back() { auto ret = dq.back(); dq.pop_back(); return ret; }
// ll pop_front() { auto ret = dq.front(); dq.pop_front(); return ret; }
// int qrypoint(ll x) {
// if (dq.empty()) return 0;
// int l = 0, r = (int) dq.size() - 1, mid;
// while (l < r) {
// mid = l + r >> 1;
// if (F(dq[mid], x) <= F(dq[mid+1], x))
// r = mid;
// else
// l = mid+1;
// }
// return dq[l];
// //return dq[l].first;
// }
// void clear() {
// deque<ll>().swap(dq);
// }
//};
// put to b
int all_line[MAX_N];
struct minconv {
int h, e;
minconv(int i) {
h = all_line[i] = i;
e = h + 1;
}
minconv() { h = e = 0; }
int size() { return e - h; }
// make sure that line has the minimum slope
void pf(int line) {
while (e-h > 1) {
auto a = all_line[h], b = all_line[h+1];
if (inter(line, a) < inter(a, b)) break;
++h;
}
all_line[--h] = line;
}
void pb(int line) {
while (e-h > 1) {
auto a = all_line[e-2], b = all_line[e-1];
if (inter(a, b) < inter(b, line)) break;
--e;
}
all_line[e++] = line;
}
int pop_front() { return all_line[h++]; }
int pop_back() { return all_line[--e]; }
int qrypoint(ll x) {
int l = h, r = e - 1, mid;
while (l < r) {
mid = l + r >> 1;
if (F(all_line[mid], x) <= F(all_line[mid+1], x))
r = mid;
else
l = mid+1;
}
return all_line[l];
}
};
void merge_conv(minconv &a, minconv &b) {
if (a.size() < b.size())
while (a.size()) b.pf(a.pop_back());
else {
while (b.size()) a.pb(b.pop_front());
swap(a, b);
}
}
vector<int> stk;
vector<minconv> conv;
vector<int> bst;
void solve() {
fill(dp, dp + m, inf);
fill(sp, sp + m, X / T + 10);
sort(s, s + n);
sort(man, man + m);
for (int i = 0;i < n;++i) {
ll spt = s[i] / T;
int p = lower_bound(man, man + m, make_pair(s[i] % T, 0ll)) - man;
chmin(sp[p-1], spt);
}
init_cost();
dp[0] = (X / T + (X % T > man[0].first)) * W;
stk.pb(0);
conv.pb();// conv[0].pb(get_line(0));
conv[0].pb(0);
bst.pb(0);
sp[0] = 0;
for (int i = 1;i < m;++i) {
auto [d, c] = man[i];
ll sum = (X / T + (X % T > d)) * W ;
int id = conv.back().qrypoint( sp[i-1] * W );
//int id = conv.back().qq(i);
if (bst.size() > 1)
chmin(dp[i], sum + cost(end(bst)[-2], i));
chmin(dp[i], sum + cost(id, i));
if (cost(id, i) <= cost(bst.back(), i))
bst.back() = id;
minconv cur;
while (stk.size()) {
int r = stk.back();
if (sp[r] < sp[i]) break;
merge_conv(conv.back(), cur);
bst.pop_back();
conv.pop_back();
stk.pop_back();
}
bst.pb(bst.empty() ? 0 : bst.back());
stk.pb(i);
conv.pb();
cur.pb(i);
swap(cur, conv.back());
}
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> X >> n >> m >> W >> T;
DE(X, n, m, W, T);
for (int i = 0;i < n;++i)
cin >> s[i];
s[n++] = X;
for (int i = 0;i < m;++i) {
auto &[d, c] = man[i];
cin >> d >> c;
}
man[m++] = make_pair(0, inf);
solve();
ll res = inf;
ll req = (X / T + 10), sum = 0;
for (int i = m-1;i >= 0;--i) {
chmin(res, dp[i] + sum);
chmin(req, sp[i]);
sum += req * W + man[i].second;
}
cout << res << '\n';
}
Compilation message
coach.cpp: In function 'void init_cost()':
coach.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
coach.cpp:44:2: note: in expansion of macro 'debug'
44 | debug(sp, sp+m);
| ^~~~~
coach.cpp: In member function 'int minconv::qrypoint(ll)':
coach.cpp:233:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
233 | mid = l + r >> 1;
| ~~^~~
coach.cpp: In function 'int32_t main()':
coach.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
coach.cpp:321:2: note: in expansion of macro 'DE'
321 | DE(X, n, m, W, T);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
