#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> ii;
const int MAX = 1e5 + 5;
const long long INF = 1e18;
bool markLow[MAX];
vector<ii> g[MAX];
vector<long long> S[MAX];
vector<vector<long long>> f[MAX];
struct FenwickTreeLow {
int n;
vector<int> buffer;
vector<long long> tree;
FenwickTreeLow(int _n) {
n = _n;
tree.resize(n + 5, -INF);
}
void update(int idx, long long val) {
idx++;
for (int i = idx; i <= n; i += i & -i) {
buffer.push_back(i);
tree[i] = max(tree[i], val);
}
}
long long get(int idx) {
idx++;
long long rs = 0;
for (int i = idx; i > 0; i -= i & -i)
rs = max(rs, tree[i]);
return rs;
}
void reset() {
for (int id: buffer)
tree[id] = -INF;
buffer.clear();
}
};
struct FenwickTreeHigh {
int n;
vector<int> buffer;
vector<long long> tree;
FenwickTreeHigh(int _n) {
n = _n;
tree.resize(n + 5, -INF);
}
void update(int idx, long long val) {
idx++;
for (int i = idx; i > 0; i -= i & -i) {
buffer.push_back(i);
tree[i] = max(tree[i], val);
}
}
long long get(int idx) {
idx++;
long long rs = 0;
for (int i = idx; i <= n; i += i & -i)
rs = max(rs, tree[i]);
return rs;
}
void reset() {
for (int id: buffer)
tree[id] = -INF;
buffer.clear();
}
};
//long long calcCost(int col, int L, int R) {
// int l = lower_bound(g[col].begin(), g[col].end(), ii(L, 0)) - g[col].begin();
// int r = upper_bound(g[col].begin(), g[col].end(), ii(R, 0)) - g[col].begin() - 1;
// if (l <= r)
// return S[col][r] - (l ? S[col][l - 1] : 0);
// return 0;
//}
long long calcCostLeft(int col, int L) {
int l = lower_bound(g[col].begin(), g[col].end(), ii(L, 0)) - g[col].begin();
return l ? S[col][l - 1] : 0;
}
long long calcCostRight(int col, int R) {
int r = upper_bound(g[col].begin(), g[col].end(), ii(R, INF)) - g[col].begin() - 1;
return r >= 0 ? S[col][r] : 0;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int i = 0; i < M; i++) {
g[X[i]].emplace_back(Y[i], W[i]);
if (!Y[i])
markLow[X[i]] = true;
}
for (int i = 0; i < N; i++) {
if (!markLow[i])
g[i].emplace_back(0, 0);
g[i].emplace_back(N, 0);
}
for (int i = 0; i < N; i++) {
sort(g[i].begin(), g[i].end());
S[i].resize(g[i].size());
S[i][0] = g[i][0].second;
for (int j = 1; j < g[i].size(); j++)
S[i][j] = S[i][j - 1] + g[i][j].second;
f[i].resize(g[i].size(), vector<long long>(2));
}
FenwickTreeLow lowTree(N), lowJump(N);
FenwickTreeHigh highTree(N), highJump(N);
long long rs = 0;
for (int i = 1; i < N; i++) {
if (i > 1) {
lowJump.reset(), highJump.reset();
for (int t = 0; t < g[i - 2].size(); t++) {
lowJump.update(t, f[i - 2][t][1]);
highJump.update(t, f[i - 2][t][1] + calcCostRight(i - 1, g[i - 2][t].first));
}
}
lowTree.reset(), highTree.reset();
for (int t = 0; t < g[i - 1].size(); t++) {
lowTree.update(t, f[i - 1][t][0] - calcCostLeft(i - 1, g[i - 1][t].first));
highTree.update(t, f[i - 1][t][1] + calcCostRight(i, g[i - 1][t].first));
}
for (int j = 0; j < g[i].size(); j++) {
if (i > 1) {
int low = upper_bound(g[i - 2].begin(), g[i - 2].end(), ii(g[i][j].first, INF)) - g[i - 2].begin() - 1;
long long tmp = lowJump.get(low) + calcCostRight(i - 1, g[i][j].first);
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
int high = low + 1;
tmp = highJump.get(high);
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
// for (int t = 0; t < g[i - 2].size(); t++) {
// long long tmp = f[i - 2][t][1] + calcCost(i - 1, 0, max(g[i - 2][t].first, g[i][j].first));
// f[i][j][0] = max(f[i][j][0], tmp);
// f[i][j][1] = max(f[i][j][1], tmp);
// }
} else {
long long tmp = calcCostRight(0, g[i][j].first);
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
}
int low = upper_bound(g[i - 1].begin(), g[i - 1].end(), ii(g[i][j].first, INF)) - g[i - 1].begin() - 1;
long long tmp = lowTree.get(low) + calcCostRight(i - 1, g[i][j].first);
f[i][j][0] = max(f[i][j][0], tmp);
f[i][j][1] = max(f[i][j][1], tmp);
int high = lower_bound(g[i - 1].begin(), g[i - 1].end(), ii(g[i][j].first, 0)) - g[i - 1].begin();
f[i][j][1] = max(f[i][j][1], highTree.get(high) - calcCostLeft(i, g[i][j].first));
rs = max({rs, f[i][j][0], f[i][j][1]});
// for (int t = 0; t < g[i - 1].size(); t++) {
// if (g[i - 1][t].first <= g[i][j].first) {
// f[i][j][0] = max(f[i][j][0], f[i - 1][t][0] + calcCost(i - 1, g[i - 1][t].first, g[i][j].first));
// f[i][j][1] = max(f[i][j][1], f[i - 1][t][0] + calcCost(i - 1, g[i - 1][t].first, g[i][j].first));
// }
// if (g[i - 1][t].first >= g[i][j].first)
// f[i][j][1] = max(f[i][j][1], f[i - 1][t][1] + calcCost(i, g[i][j].first, g[i - 1][t].first));
// }
}
}
return rs;
}
//int main() {
// freopen("../_input", "r", stdin);
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
//
// std::vector<int> X(M), Y(M), W(M);
// for (int i = 0; i < M; ++i) {
// assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
// }
//
// long long result = max_weights(N, M, X, Y, W);
// printf("%lld\n", result);
// return 0;
//}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:112:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int j = 1; j < g[i].size(); j++)
| ~~^~~~~~~~~~~~~
fish.cpp:122:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int t = 0; t < g[i - 2].size(); t++) {
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:128:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for (int t = 0; t < g[i - 1].size(); t++) {
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int j = 0; j < g[i].size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
51668 KB |
Output is correct |
| 2 |
Correct |
237 ms |
58016 KB |
Output is correct |
| 3 |
Correct |
121 ms |
30832 KB |
Output is correct |
| 4 |
Correct |
123 ms |
30764 KB |
Output is correct |
| 5 |
Correct |
430 ms |
77484 KB |
Output is correct |
| 6 |
Correct |
464 ms |
63252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 2 |
Incorrect |
317 ms |
60056 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '40604944491929' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
30796 KB |
Output is correct |
| 2 |
Correct |
120 ms |
30836 KB |
Output is correct |
| 3 |
Incorrect |
138 ms |
30028 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 6 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 8 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
7380 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '219109041335' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 6 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 8 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
7380 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '219109041335' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 6 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 8 |
Correct |
3 ms |
7252 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
7380 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '219109041335' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
30796 KB |
Output is correct |
| 2 |
Correct |
120 ms |
30836 KB |
Output is correct |
| 3 |
Incorrect |
138 ms |
30028 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
51668 KB |
Output is correct |
| 2 |
Correct |
237 ms |
58016 KB |
Output is correct |
| 3 |
Correct |
121 ms |
30832 KB |
Output is correct |
| 4 |
Correct |
123 ms |
30764 KB |
Output is correct |
| 5 |
Correct |
430 ms |
77484 KB |
Output is correct |
| 6 |
Correct |
464 ms |
63252 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 8 |
Incorrect |
317 ms |
60056 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '40604944491929' |
| 9 |
Halted |
0 ms |
0 KB |
- |
