#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fs first
#define sc second
const int N = 500005;
vector<pair<int, int>> a[N];
int tl[2 * N], tr[2 * N];
int ql(int l, int r) {
int res = -1e9;
for (l += N, r += N + 1; l < r; l /= 2, r /= 2) {
if (l & 1) res = max(res, tl[l++]);
if (r & 1) res = max(res, tl[--r]);
}
return res;
}
int qr(int l, int r) {
int res = -1e9;
for (l += N, r += N + 1; l < r; l /= 2, r /= 2) {
if (l & 1) res = max(res, tr[l++]);
if (r & 1) res = max(res, tr[--r]);
}
return res;
}
void cl(int x, int v) {
x += N; if (tl[x] >= v) return;
for (tl[x] = v; x > 1; x /= 2) {
tl[x / 2] = max(tl[x], tl[x ^ 1]);
}
}
void cr(int x, int v) {
x += N; if (tr[x] >= v) return;
for (tr[x] = v; x > 1; x /= 2) {
tr[x / 2] = max(tr[x], tr[x ^ 1]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, lc, rc, s;
cin >> n >> lc >> rc >> s;
for (int i = 0; i < n; ++i) {
int t, l, x;
cin >> t >> l >> x;
a[t].push_back({l, x});
}
a[N - 1].push_back({s, 0});
for (int i = 0; i < N; ++i) {
sort(a[i].begin(), a[i].end());
}
for (int i = 0; i < N; ++i) {
tl[N + i] = tr[N + i] = -1e9;
if (i == s) {
tl[N + i] = i * rc;
tr[N + i] = (N - 1 - i) * lc;
}
}
for (int i = N - 1; i > 0; --i) {
tr[i] = max(tr[2 * i], tr[2 * i + 1]);
tl[i] = max(tl[2 * i], tl[2 * i + 1]);
}
for (int t = 0; t < N; ++t) {
vector<int> res;
int lp = 0, lv = -1e9;
for (int i = 0; i < a[t].size(); ++i) {
int v = lv + a[t][i].sc - (a[t][i].fs - lp) * rc;
v = max(v, a[t][i].sc - rc * a[t][i].fs + ql(0, a[t][i].fs));
res.push_back(v);
lv = v; lp = a[t][i].fs;
}
lp = N - 1; lv = -1e9;
for (int i = a[t].size() - 1; i >= 0; --i) {
int v = lv + a[t][i].sc - (lp - a[t][i].fs) * lc;
v = max(v, a[t][i].sc - lc * (N - 1 - a[t][i].fs) + qr(a[t][i].fs, N - 1));
lv = v; lp = a[t][i].fs;
res[i] = max(res[i], v);
}
for (int i = 0; i < a[t].size(); ++i) {
cl(a[t][i].fs, res[i] + a[t][i].fs * rc);
cr(a[t][i].fs, res[i] + (N - 1 - a[t][i].fs) * lc);
}
// if (res.size()) {
// cout << "! " << t << '\n';
// for (auto x: res) {
// cout << x << ' ';
// }
// cout << '\n';
// }
if (t + 1 == N) {
cout << res[0] << "\n";
}
}
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < a[t].size(); ++i) {
| ~~^~~~~~~~~~~~~
salesman.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i = 0; i < a[t].size(); ++i) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19972 KB |
Output is correct |
| 2 |
Correct |
6 ms |
19804 KB |
Output is correct |
| 3 |
Correct |
8 ms |
19848 KB |
Output is correct |
| 4 |
Correct |
9 ms |
20108 KB |
Output is correct |
| 5 |
Correct |
9 ms |
20060 KB |
Output is correct |
| 6 |
Correct |
20 ms |
21008 KB |
Output is correct |
| 7 |
Correct |
44 ms |
22364 KB |
Output is correct |
| 8 |
Correct |
95 ms |
24924 KB |
Output is correct |
| 9 |
Correct |
126 ms |
27068 KB |
Output is correct |
| 10 |
Correct |
214 ms |
33876 KB |
Output is correct |
| 11 |
Correct |
272 ms |
34916 KB |
Output is correct |
| 12 |
Correct |
311 ms |
38632 KB |
Output is correct |
| 13 |
Correct |
328 ms |
38736 KB |
Output is correct |
| 14 |
Correct |
433 ms |
44608 KB |
Output is correct |
| 15 |
Correct |
346 ms |
43552 KB |
Output is correct |
| 16 |
Correct |
409 ms |
43528 KB |
Output is correct |
| 17 |
Incorrect |
7 ms |
19840 KB |
Output isn't correct |
| 18 |
Incorrect |
7 ms |
19840 KB |
Output isn't correct |
| 19 |
Incorrect |
7 ms |
20060 KB |
Output isn't correct |
| 20 |
Incorrect |
8 ms |
20060 KB |
Output isn't correct |
| 21 |
Incorrect |
10 ms |
20096 KB |
Output isn't correct |
| 22 |
Incorrect |
9 ms |
19980 KB |
Output isn't correct |
| 23 |
Incorrect |
9 ms |
20060 KB |
Output isn't correct |
| 24 |
Incorrect |
9 ms |
20056 KB |
Output isn't correct |
| 25 |
Incorrect |
54 ms |
22268 KB |
Output isn't correct |
| 26 |
Incorrect |
96 ms |
24964 KB |
Output isn't correct |
| 27 |
Incorrect |
159 ms |
28536 KB |
Output isn't correct |
| 28 |
Incorrect |
195 ms |
29516 KB |
Output isn't correct |
| 29 |
Incorrect |
237 ms |
31252 KB |
Output isn't correct |
| 30 |
Incorrect |
235 ms |
33264 KB |
Output isn't correct |
