| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 627598 | dqhungdl | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
//}