#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>
using namespace std;
// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define derr if(1) cerr
typedef vector<int> vi;
// END NO SAD
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> matrix;
typedef pair<ll, ll> pll;
int downcost, upcost;
const int KOOSAGA_SZ = 1 << 19;
pll forupstream[2 * KOOSAGA_SZ];
pll upstreammerge(pll a, pll b) {
if(a.first < b.first) swap(a, b);
ll areal = a.second - (a.first - b.first) * upcost;
if(areal >= b.second) return a;
return b;
}
void upset(int idx, ll val) {
forupstream[idx + KOOSAGA_SZ] = {idx, val};
idx += KOOSAGA_SZ;
while(idx > 1) {
idx /= 2;
forupstream[idx] = upstreammerge(forupstream[2*idx], forupstream[2*idx+1]);
}
}
pll upqry(int lhs, int rhs) {
pll ret = {0, -1e18};
lhs += KOOSAGA_SZ;
rhs += KOOSAGA_SZ;
while(lhs <= rhs) {
if(lhs == rhs) return upstreammerge(ret, forupstream[lhs]);
if(lhs%2) ret = upstreammerge(ret, forupstream[lhs++]);
if(rhs%2==0) ret = upstreammerge(ret, forupstream[rhs--]);
lhs /= 2;
rhs /= 2;
}
return ret;
}
pll fordownstream[2 * KOOSAGA_SZ];
pll downstreammerge(pll a, pll b) {
if(a.first > b.first) swap(a, b);
ll areal = a.second - (b.first - a.first) * downcost;
if(areal >= b.second) return a;
return b;
}
void downset(int idx, ll val) {
fordownstream[idx + KOOSAGA_SZ] = {idx, val};
idx += KOOSAGA_SZ;
while(idx > 1) {
idx /= 2;
fordownstream[idx] = downstreammerge(fordownstream[2*idx], fordownstream[2*idx+1]);
}
}
pll downqry(int lhs, int rhs) {
pll ret = {0, -1e18};
lhs += KOOSAGA_SZ;
rhs += KOOSAGA_SZ;
while(lhs <= rhs) {
if(lhs == rhs) return downstreammerge(ret, fordownstream[lhs]);
if(lhs%2) ret = downstreammerge(ret, fordownstream[lhs++]);
if(rhs%2==0) ret = downstreammerge(ret, fordownstream[rhs--]);
lhs /= 2;
rhs /= 2;
}
return ret;
}
struct event {
int t;
int x;
int gain;
event(int a, int b, int c) {
t=a;
x=b;
gain=c;
}
bool operator<(const event& e) {
return t < e.t;
}
};
bool locsort(event& a, event& b) {
return a.x < b.x;
}
void solve() {
vector<event> events;
int n, start;
cin >> n >> upcost >> downcost >> start;
for(int i = 0; i < KOOSAGA_SZ; i++) {
upset(i, -1e18);
downset(i, -1e18);
}
upset(start, 0);
downset(start, 0);
for(int i = 0; i < n; i++) {
int t, x, gain;
cin >> t >> x >> gain;
events.emplace_back(t, x, gain);
}
events.emplace_back(1000000, start, 0);
sort(all(events));
for(int i = 0; i < sz(events);) {
int j = i+1;
while(j < sz(events) && events[i].t == events[j].t) {
j++;
}
vector<event> window;
for(int k = i; k < j; k++) {
window.push_back(events[k]);
}
sort(all(window), locsort);
vector<ll> singlegain;
for(int a = 0; a < sz(window); a++) {
pll comedown = downqry(0, window[a].x - 1);
pll comeup = upqry(window[a].x+1, KOOSAGA_SZ-1);
singlegain.push_back(
max(
comedown.second - downcost * (window[a].x - comedown.first),
comeup.second - upcost * (comeup.first - window[a].x)
) + window[a].gain
);
// derr << "single gain for event at " << window[a].x << " is tentatively " << singlegain.back() << endl;
}
vector<ll> downgain;
for(int a = 0; a < sz(singlegain); a++) {
downgain.push_back(singlegain[a]);
}
for(int a = 1; a < sz(singlegain); a++) {
downgain[a] = max(downgain[a], downgain[a-1] - downcost * (window[a].x - window[a-1].x) + window[a].gain);
}
vector<ll> upgain;
for(int a = 0; a < sz(singlegain); a++) {
upgain.push_back(singlegain[a]);
}
for(int a = sz(singlegain)-2; a >= 0; a--) {
upgain[a] = max(upgain[a], upgain[a+1] - upcost * (window[a+1].x - window[a].x) + window[a].gain);
}
for(int a = 0; a < sz(window); a++) {
downset(window[a].x, max(downgain[a], upgain[a]));
upset(window[a].x, max(downgain[a], upgain[a]));
}
i = j;
}
pll ret = downqry(start, start);
cout << max(0LL, ret.second) << "\n";
}
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
155 ms |
33400 KB |
Output is correct |
| 3 |
Correct |
155 ms |
33176 KB |
Output is correct |
| 4 |
Correct |
157 ms |
33272 KB |
Output is correct |
| 5 |
Correct |
159 ms |
33400 KB |
Output is correct |
| 6 |
Correct |
181 ms |
34128 KB |
Output is correct |
| 7 |
Correct |
229 ms |
34804 KB |
Output is correct |
| 8 |
Correct |
305 ms |
36212 KB |
Output is correct |
| 9 |
Correct |
372 ms |
38892 KB |
Output is correct |
| 10 |
Correct |
534 ms |
43872 KB |
Output is correct |
| 11 |
Correct |
609 ms |
44384 KB |
Output is correct |
| 12 |
Correct |
765 ms |
44120 KB |
Output is correct |
| 13 |
Correct |
764 ms |
44512 KB |
Output is correct |
| 14 |
Correct |
944 ms |
48120 KB |
Output is correct |
| 15 |
Correct |
786 ms |
47196 KB |
Output is correct |
| 16 |
Correct |
909 ms |
47276 KB |
Output is correct |
| 17 |
Correct |
152 ms |
33144 KB |
Output is correct |
| 18 |
Correct |
153 ms |
33144 KB |
Output is correct |
| 19 |
Correct |
153 ms |
33184 KB |
Output is correct |
| 20 |
Correct |
155 ms |
33400 KB |
Output is correct |
| 21 |
Correct |
159 ms |
33276 KB |
Output is correct |
| 22 |
Correct |
158 ms |
33528 KB |
Output is correct |
| 23 |
Correct |
159 ms |
33320 KB |
Output is correct |
| 24 |
Correct |
160 ms |
33400 KB |
Output is correct |
| 25 |
Correct |
277 ms |
35952 KB |
Output is correct |
| 26 |
Correct |
393 ms |
39780 KB |
Output is correct |
| 27 |
Correct |
575 ms |
45788 KB |
Output is correct |
| 28 |
Correct |
623 ms |
44888 KB |
Output is correct |
| 29 |
Correct |
782 ms |
46040 KB |
Output is correct |
| 30 |
Correct |
787 ms |
50860 KB |
Output is correct |
