#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
const int MAX = 1e5 + 5, SINF = 2e9;
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, SINF)) - 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, SINF)) - 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, SINF)) - 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]));
// }#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
const int MAX = 1e5 + 5, SINF = 2e9;
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, SINF)) - 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, SINF)) - 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, SINF)) - 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;
//}
//
// 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<int, 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<int, 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<int, 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<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int j = 0; j < g[i].size(); j++) {
| ~~^~~~~~~~~~~~~
fish.cpp: At global scope:
fish.cpp:190:11: error: redefinition of 'const int MAX'
190 | const int MAX = 1e5 + 5, SINF = 2e9;
| ^~~
fish.cpp:6:11: note: 'const int MAX' previously defined here
6 | const int MAX = 1e5 + 5, SINF = 2e9;
| ^~~
fish.cpp:190:26: error: redefinition of 'const int SINF'
190 | const int MAX = 1e5 + 5, SINF = 2e9;
| ^~~~
fish.cpp:6:26: note: 'const int SINF' previously defined here
6 | const int MAX = 1e5 + 5, SINF = 2e9;
| ^~~~
fish.cpp:191:17: error: redefinition of 'const long long int INF'
191 | const long long INF = 1e18;
| ^~~
fish.cpp:7:17: note: 'const long long int INF' previously defined here
7 | const long long INF = 1e18;
| ^~~
fish.cpp:192:6: error: redefinition of 'bool markLow [100005]'
192 | bool markLow[MAX];
| ^~~~~~~
fish.cpp:8:6: note: 'bool markLow [100005]' previously declared here
8 | bool markLow[MAX];
| ^~~~~~~
fish.cpp:193:12: error: redefinition of 'std::vector<std::pair<int, int> > g [100005]'
193 | vector<ii> g[MAX];
| ^
fish.cpp:9:12: note: 'std::vector<std::pair<int, int> > g [100005]' previously declared here
9 | vector<ii> g[MAX];
| ^
fish.cpp:194:19: error: redefinition of 'std::vector<long long int> S [100005]'
194 | vector<long long> S[MAX];
| ^
fish.cpp:10:19: note: 'std::vector<long long int> S [100005]' previously declared here
10 | vector<long long> S[MAX];
| ^
fish.cpp:195:27: error: redefinition of 'std::vector<std::vector<long long int> > f [100005]'
195 | vector<vector<long long>> f[MAX];
| ^
fish.cpp:11:27: note: 'std::vector<std::vector<long long int> > f [100005]' previously declared here
11 | vector<vector<long long>> f[MAX];
| ^
fish.cpp:197:8: error: redefinition of 'struct FenwickTreeLow'
197 | struct FenwickTreeLow {
| ^~~~~~~~~~~~~~
fish.cpp:13:8: note: previous definition of 'struct FenwickTreeLow'
13 | struct FenwickTreeLow {
| ^~~~~~~~~~~~~~
fish.cpp:230:8: error: redefinition of 'struct FenwickTreeHigh'
230 | struct FenwickTreeHigh {
| ^~~~~~~~~~~~~~~
fish.cpp:46:8: note: previous definition of 'struct FenwickTreeHigh'
46 | struct FenwickTreeHigh {
| ^~~~~~~~~~~~~~~
fish.cpp:271:11: error: redefinition of 'long long int calcCostLeft(int, int)'
271 | long long calcCostLeft(int col, int L) {
| ^~~~~~~~~~~~
fish.cpp:87:11: note: 'long long int calcCostLeft(int, int)' previously defined here
87 | long long calcCostLeft(int col, int L) {
| ^~~~~~~~~~~~
fish.cpp:276:11: error: redefinition of 'long long int calcCostRight(int, int)'
276 | long long calcCostRight(int col, int R) {
| ^~~~~~~~~~~~~
fish.cpp:92:11: note: 'long long int calcCostRight(int, int)' previously defined here
92 | long long calcCostRight(int col, int R) {
| ^~~~~~~~~~~~~
fish.cpp:281:11: error: redefinition of 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)'
281 | long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
| ^~~~~~~~~~~
fish.cpp:97:11: note: 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)' previously defined here
97 | long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
| ^~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:296:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
296 | for (int j = 1; j < g[i].size(); j++)
| ~~^~~~~~~~~~~~~
fish.cpp:306:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
306 | for (int t = 0; t < g[i - 2].size(); t++) {
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:312:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
312 | for (int t = 0; t < g[i - 1].size(); t++) {
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:316:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
316 | for (int j = 0; j < g[i].size(); j++) {
| ~~^~~~~~~~~~~~~
