#include <bits/stdc++.h>
using namespace std;
// supports: point modify, range apply, range query, walk to find first/last with some precedent
// you are to implement the 2 structs Tag and Info
// for the walks, pass a lambda that takes in Info and return true iff the node with that Info will contain the desired element
template<class Info, class Tag>
struct LazySegmentTree {
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(vector<Info>(n_, v_));
}
template<class T>
void init(vector<T> init_) {
n = init_.size();
info.assign(4 << __lg(n), Info());
tag.assign(4 << __lg(n), Tag());
function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
push(p);
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F &&pred) {
return findLast(1, 0, n, l, r, pred);
}
};
struct Tag {
void apply(const Tag &t) & {
}
};
struct Info {
long long sum;
long long premax;
long long sufmax;
long long allmax;
Info() {
sum = premax = sufmax = allmax = 0;
}
Info(int x) {
sum = x;
premax = sufmax = allmax = max(0, x);
}
void apply(const Tag &t) & {
}
Info operator+(const Info &b) {
Info res;
res.sum = sum + b.sum;
res.premax = max(premax, sum + b.premax);
res.sufmax = max(sufmax + b.sum, b.sufmax);
res.allmax = max({ allmax, b.allmax, sufmax + b.premax });
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<array<int, 2>> a(n);
vector<int> w(n);
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1] >> w[i];
}
auto norm = [&](array<int, 2> p) -> long long {
return 1LL * p[0] * p[0] + 1LL * p[1] * p[1];
};
vector<pair<vector<int>, vector<int>>> instructions = [&] { // Give list of instructions, each try to sorts a certain subset
struct Fraction {
const int INF = 2e9 + 10;
int num, den;
Fraction(int num, int den) {
if (den < 0) num *= -1, den *= -1;
if (den == 0) {
assert(num != 0);
if (num > 0) num = INF;
else num = -INF;
den = 1;
}
this->num = num;
this->den = den;
}
bool operator<(Fraction other) {
return 1LL * num * other.den < 1LL * other.num * den;
}
bool operator==(Fraction other) {
return 1LL * num * other.den == 1LL * other.num * den;
}
bool operator>(Fraction other) {
return 1LL * num * other.den > 1LL * other.num * den;
}
bool operator!=(Fraction other) {
return !(*this == other);
}
Fraction operator=(Fraction other) {
this->num = other.num;
this->den = other.den;
return *this;
}
};
vector<pair<Fraction, array<int, 2>>> fetch;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
auto [x0, y0] = a[i];
auto [x1, y1] = a[j];
Fraction tan_theta(x0 - x1, y0 - y1);
if (tan_theta == Fraction(1, 0)) continue;
fetch.push_back(make_pair(tan_theta, array<int, 2>{i, j}));
}
}
sort(fetch.begin(), fetch.end(), [&](auto F, auto S) -> bool {
auto [frac0, ij0] = F;
auto [i0, j0] = ij0;
auto [frac1, ij1] = S;
auto [i1, j1] = ij1;
return frac0 < frac1;
});
vector<pair<vector<int>, vector<int>>> res;
for (int i = 0; i < fetch.size(); ) {
Fraction tan_theta = fetch[i].first;
vector<int> ids;
ids.push_back(fetch[i].second[0]);
ids.push_back(fetch[i].second[1]);
int j = i + 1;
while (j < fetch.size() && fetch[i].first == fetch[j].first) {
ids.push_back(fetch[j].second[0]);
ids.push_back(fetch[j].second[1]);
j++;
}
sort(ids.begin(), ids.end());
ids.resize(unique(ids.begin(), ids.end()) - ids.begin());
i = j;
sort(ids.begin(), ids.end(), [&](int i, int j) -> bool {
if (Fraction(a[i][0] - a[j][0], a[i][1] - a[j][1]) != tan_theta) {
return (a[i][1] - a[j][1] < 0) ^ (Fraction(a[i][0] - a[j][0], a[i][1] - a[j][1]) < tan_theta);
}
return false;
// return (a[i][0] - a[j][0] < 0) ^ (Fraction(a[j][1] - a[i][1], a[i][0] - a[j][0]) > tan_theta);
});
vector<int> unstable = ids;
sort(ids.begin(), ids.end(), [&](int i, int j) -> bool {
if (Fraction(a[i][0] - a[j][0], a[i][1] - a[j][1]) != tan_theta) {
return (a[i][1] - a[j][1] < 0) ^ (Fraction(a[i][0] - a[j][0], a[i][1] - a[j][1]) < tan_theta);
}
return false;
// return (a[i][0] - a[j][0] < 0) ^ (Fraction(a[j][1] - a[i][1], a[i][0] - a[j][0]) < tan_theta);
});
vector<int> stable = ids;
res.push_back(make_pair(unstable, stable));
}
return res;
}();
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) {
if (a[i][1] != a[j][1]) return a[i][1] < a[j][1];
return a[i][0] > a[j][0];
});
vector<int> ip(n);
for (int i = 0; i < n; i++) {
ip[p[i]] = i;
}
LazySegmentTree<Info, Tag> seg(n);
for (int i = 0; i < n; i++) {
seg.modify(i, w[p[i]]);
}
long long ans = seg.rangeQuery(0, n).allmax;
for (auto [unstable, stable] : instructions) {
vector<int> positions;
for (int x : unstable) {
positions.push_back(ip[x]);
}
sort(positions.begin(), positions.end());
int ii = 0;
for (int i : positions) {
p[i] = unstable[ii++];
seg.modify(i, w[p[i]]);
ip[p[i]] = i;
}
ans = max(ans, seg.rangeQuery(0, n).allmax);
ii = 0;
for (int i : positions) {
p[i] = stable[ii++];
seg.modify(i, w[p[i]]);
ip[p[i]] = i;
}
ans = max(ans, seg.rangeQuery(0, n).allmax);
}
cout << ans << '\n';
}
Compilation message
bulldozer.cpp: In lambda function:
bulldozer.cpp:245:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
245 | for (int i = 0; i < fetch.size(); ) {
| ~~^~~~~~~~~~~~~~
bulldozer.cpp:251:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
251 | while (j < fetch.size() && fetch[i].first == fetch[j].first) {
| ~~^~~~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:190:10: warning: variable 'norm' set but not used [-Wunused-but-set-variable]
190 | auto norm = [&](array<int, 2> p) -> long long {
| ^~~~
bulldozer.cpp: In instantiation of 'main()::<lambda()>::<lambda(auto:23, auto:24)> [with auto:23 = std::pair<main()::<lambda()>::Fraction, std::array<int, 2> >; auto:24 = std::pair<main()::<lambda()>::Fraction, std::array<int, 2> >]':
/usr/include/c++/10/bits/predefined_ops.h:156:30: required from 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> >*, std::vector<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> > > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> >*, std::vector<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> > > >; _Compare = main()::<lambda()>::<lambda(auto:23, auto:24)>]'
/usr/include/c++/10/bits/stl_algo.h:82:17: required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> >*, std::vector<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda()>::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34: required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> >*, std::vector<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda()>::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> >*, std::vector<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> > > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda()>::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> >*, std::vector<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda()>::<lambda(auto:23, auto:24)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18: required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> >*, std::vector<std::pair<main()::<lambda()>::Fraction, std::array<int, 2> > > >; _Compare = main()::<lambda()>::<lambda(auto:23, auto:24)>]'
bulldozer.cpp:243:10: required from here
bulldozer.cpp:239:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
239 | auto [i0, j0] = ij0;
| ^~~~~~~~
bulldozer.cpp:241:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
241 | auto [i1, j1] = ij1;
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
