#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define int long long
using namespace std;
const int N = 3e5 + 10;
int order[N];
vector<int> fish[N];
vector<long long> pref[N];
long long in[N], de[N], lastin[N], lastde[2][N];
long long calc(int h, int col) {
if (h == -1 || col < 0 || fish[col].empty()) return 0;
int idx = --upper_bound(fish[col].begin(), fish[col].end(), h) - fish[col].begin();
return pref[col][idx];
}
long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
for(int i = 0; i < n; i++) fish[i].push_back(0), pref[i].push_back(0);
for(int i = 0; i < m; i++) order[i] = i;
sort(order, order + m, [&] (const int &A, const int &B) {
return Y[A] < Y[B];
});
for(int cur = 0; cur < m; cur++) {
int i = order[cur];
fish[X[i]].push_back(Y[i]);
pref[X[i]].push_back(pref[X[i]].back() + W[i]);
}
for(int i = 0; i < n; i++) fish[i].push_back(n + 1);
de[0] = calc(n, 1);
for(int i = 1; i < n; i++) {
for(int &preh : fish[i]) {
int h = preh - 1;
in[i] = max(in[i], in[i - 1] + calc(h, i - 1) - calc(h, i));
de[i] = max(de[i], de[i - 1] - calc(h, i) + calc(h, i + 1));
lastde[1][i] = max(lastde[1][i], de[i - 1] - calc(h, i) + calc(h, i + 1));
lastde[0][i] = max(lastde[0][i], de[i - 1] - calc(h, i));
lastin[i] = max(lastin[i], in[i] + calc(n, i) - calc(h, i));
if (i > 2) {
long long tmp = max(lastde[1][i - 2], lastde[0][i - 2] + calc(h, i - 1));
in[i] = max(in[i], tmp - calc(h, i));
de[i] = max(de[i], lastin[i - 2] + calc(n, i) - calc(h, i) + calc(h, i + 1));
}
}
}
// cout << max(in[n - 1], de[n - 1]);
return max(in[n - 1], de[n - 1]);
}
#ifdef ngu
main() {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
int n, m; cin >> n >> m;
vector<int> x(m), y(m), w(m);
for(int i = 0; i < m; i++) cin >> x[i] >> y[i] >> w[i];
long long ret = max_weights(n, m, x, y, w);
}
#endif // ngu
Compilation message
/usr/bin/ld: /tmp/cc9Asggl.o: in function `main':
grader.cpp:(.text.startup+0x25e): undefined reference to `max_weights(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
