This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define eack emplace_back
#define all(x) (x).begin(), (x).end()
vector<int> xx;
const int SIZE = 1 << 17;
struct ST {
struct Node {
long long v = -4e18, lazy;
} A[2 * SIZE];
int sz;
void lazydown(int nn, int ns, int m, int ne) {
A[nn << 1].v += A[nn].lazy;
A[nn << 1].lazy += A[nn].lazy;
A[nn << 1 | 1].v += A[nn].lazy;
A[nn << 1 | 1].lazy += A[nn].lazy;
A[nn].lazy = 0;
}
void updateP(int nn, int ns, int ne, int x, long long v) {
if (x > ne || x < ns) return;
auto &cur = A[nn];
if (ns == ne) {
cur.v = max(cur.v, v);
return;
}
int m = ns + ne >> 1;
lazydown(nn, ns, m, ne);
updateP(nn << 1, ns, m, x, v);
updateP(nn << 1 | 1, m + 1, ne, x, v);
cur.v = max(A[nn << 1].v, A[nn << 1 | 1].v);
}
void update(int nn, int ns, int ne, int s, int e, long long v) {
if (ns > e || ne < s) return;
auto &cur = A[nn];
if (s <= ns && ne <= e) {
cur.v += v;
cur.lazy += v;
return;
}
int m = ns + ne >> 1;
lazydown(nn, ns, m, ne);
update(nn << 1, ns, m, s, e, v);
update(nn << 1 | 1, m + 1, ne, s, e, v);
cur.v = max(A[nn << 1].v, A[nn << 1 | 1].v);
}
void updateP(int x, long long v) {
updateP(1, 0, sz, x, v);
}
void update(int s, int e, long long v) {
update(1, 0, sz, s, e, v);
}
long long query() {
lazydown(1, 0, sz >> 1, sz);
return A[1].v;
}
} seg;
int T[100005], B[100005], S[100005];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int K, M, D, A, N; cin >> K >> M >> D >> A >> N;
for (int i = 1; i <= N; ++i)
cin >> T[i] >> B[i];
T[0] = K; T[N + 1] = M;
for (int i = 0; i <= N + 1; ++i) xx.eack(T[i] % D);
sort(all(xx));
xx.erase(unique(all(xx)), xx.end());
for (int i = 0; i <= N + 1; ++i) {
S[i] = lower_bound(all(xx), T[i] % D) - xx.begin();
}
seg.sz = xx.size() - 1;
seg.updateP(S[0], 0);
long long t = 0;
for (int i = 1; i <= N + 1; ++i) {
seg.update(0, seg.sz, -1ll * (T[i] - T[i - 1]) / D * A);
if (S[i] >= S[i - 1]) seg.update(S[i - 1], S[i] - 1, -A);
else {
seg.update(S[i - 1], seg.sz, -A);
seg.update(0, S[i] - 1, -A);
}
t = seg.query() + B[i];
seg.updateP(S[i], t);
}
cout << t;
return 0;
}
Compilation message (stderr)
koala.cpp: In member function 'void ST::updateP(int, int, int, int, long long int)':
koala.cpp:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns + ne >> 1;
~~~^~~~
koala.cpp: In member function 'void ST::update(int, int, int, int, int, long long int)':
koala.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns + ne >> 1;
~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |