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 int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int oo = 1e18 + 7, mod = 1e9 + 7;
const int N = 1e5 + 5;
int k, m, n, d, aa, a[N], b[N], dp[N];
set<int> remainders;
unordered_map<int, int> uomp;
struct it{
int n;
int arr[N << 2], laz[N << 2];
it(int _n): n(_n){
for(int i = 1; i <= (4 * n); i++) arr[i] = laz[i] = -oo;
}
void lazy(int id){
if(laz[id] = -oo) return;
arr[id << 1] = max(arr[id << 1], laz[id]);
laz[id << 1] = max(laz[id << 1], laz[id]);
arr[id << 1 | 1] = max(arr[id << 1 | 1], laz[id]);
laz[id << 1 | 1] = max(laz[id << 1 | 1], laz[id]);
laz[id] = -oo;
}
void update(int id, int l, int r, int L, int R, int val){
if(l > R || r < L || l > r) return;
if(l >= L && r <= R){
//cout << id << " " << val << "\n";
arr[id] = max(arr[id], val);
laz[id] = max(laz[id], val);
return;
}
lazy(id);
int mid = (l + r) >> 1;
update(id << 1, l, mid, L, R, val);
update(id << 1 | 1, mid + 1, r, L, R, val);
arr[id] = max(arr[id << 1], arr[id << 1 | 1]);
}
int get(int id, int l, int r, int L, int R){
//cout << id << " " << l << " " << r << " " << arr[id] << "\n";
if(l > R || r < L) return -oo;
if(l >= L && r <= R){
return arr[id];
}
lazy(id);
int mid = (l + r) >> 1;
return max(get(id << 1, l, mid, L, R), get(id << 1 | 1, mid + 1, r, L, R));
}
};
void input(){
cin >> k >> m >> d >> aa >> n;
for(int i = 1; i <= n; i++){
cin >> a[i] >> b[i];
}
}
void process(){
remainders.insert(k % d);
remainders.insert(m % d);
for(int i = 1; i <= n; i++) remainders.insert(a[i] % d);
int cnt = 0;
for(auto it : remainders){
cnt++;
uomp[it] = cnt;
}
for(int i = 1; i <= n + 1; i++) dp[i] = -oo;
it tmp(cnt);
a[n + 1] = m;
tmp.update(1, 1, cnt, uomp[k % d], uomp[k % d], -((k / d) * aa));
for(int i = 1; i <= n + 1; i++){
int x = tmp.get(1, 1, cnt, 1, uomp[a[i] % d] - 1);
int y = tmp.get(1, 1, cnt, uomp[a[i] % d], cnt);
// cout << x << " " << y << "\n";
dp[i] = max(x - aa, y);
//dp[i] += (a[i] / d) * aa;
dp[i] -= (a[i] / d) * aa;
dp[i] += b[i];
//cout << dp[i] << "\n";
tmp.update(1, 1, cnt, uomp[a[i] % d], uomp[a[i] % d], dp[i] + (a[i] / d) * aa);
}
}
void output(){
cout << dp[n + 1];
}
signed main(){
ios_base::sync_with_stdio(0);
input();
process();
output();
}
Compilation message (stderr)
koala.cpp: In member function 'void it::lazy(long long int)':
koala.cpp:29:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
29 | if(laz[id] = -oo) return;
| ~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |