oj.uz

Submission #1117904

# Submission time Handle Problem Language Result Execution time Memory
1117904 2024-11-24T09:36:14 Z Pannda Bulldozer (JOI17_bulldozer) C++17
25 / 100
 2000 ms 261004 KB 
#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;
    }
};

typedef long double F;

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 !(*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(); ) {
            F tan_theta = (F)fetch[i].first.num / (F)fetch[i].first.den;
            F theta = atan(tan_theta);
            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());
            sort(ids.begin(), ids.end(), [&](int i, int j) -> bool {
                F xi = cos(theta) * a[i][0] - sin(theta) * a[i][1];
                F yi = sin(theta) * a[i][0] + cos(theta) * a[i][1];
                F xj = cos(theta) * a[j][0] - sin(theta) * a[j][1];
                F yj = sin(theta) * a[j][0] + cos(theta) * a[j][1];
                if (abs(xi - xj) > 1e-7) return xi < xj;
                return yi < yj;
            });
            vector<int> unstable = ids;
            sort(ids.begin(), ids.end(), [&](int i, int j) -> bool {
                F xi = cos(theta) * a[i][0] - sin(theta) * a[i][1];
                F yi = sin(theta) * a[i][0] + cos(theta) * a[i][1];
                F xj = cos(theta) * a[j][0] - sin(theta) * a[j][1];
                F yj = sin(theta) * a[j][0] + cos(theta) * a[j][1];
                if (abs(xi - xj) > 1e-7) return xi < xj;
                return yi > yj;
            });
            vector<int> stable = ids;
            res.push_back(make_pair(unstable, stable));
            i = j;
        }
        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:244: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]
  244 |         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:192:10: warning: variable 'norm' set but not used [-Wunused-but-set-variable]
  192 |     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:242:10:   required from here
bulldozer.cpp:238:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  238 |             auto [i0, j0] = ij0;
      |                  ^~~~~~~~
bulldozer.cpp:240:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  240 |             auto [i1, j1] = ij1;
      |                  ^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1076 KB Output is correct
2 Correct 6 ms 1076 KB Output is correct
3 Correct 8 ms 1076 KB Output is correct
4 Correct 8 ms 1076 KB Output is correct
5 Correct 6 ms 1076 KB Output is correct
6 Correct 6 ms 1076 KB Output is correct
7 Correct 6 ms 1076 KB Output is correct
8 Correct 7 ms 1076 KB Output is correct
9 Correct 7 ms 1076 KB Output is correct
10 Correct 8 ms 1076 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 6 ms 1244 KB Output is correct
22 Correct 6 ms 1076 KB Output is correct
23 Correct 7 ms 1208 KB Output is correct
24 Correct 6 ms 1076 KB Output is correct
25 Correct 8 ms 1076 KB Output is correct
26 Correct 9 ms 1076 KB Output is correct
27 Correct 9 ms 1076 KB Output is correct
28 Correct 8 ms 1076 KB Output is correct
29 Correct 6 ms 1076 KB Output is correct
30 Correct 7 ms 1076 KB Output is correct
31 Correct 7 ms 1088 KB Output is correct
32 Correct 8 ms 1076 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1076 KB Output is correct
2 Correct 6 ms 1076 KB Output is correct
3 Correct 8 ms 1076 KB Output is correct
4 Correct 8 ms 1076 KB Output is correct
5 Correct 6 ms 1076 KB Output is correct
6 Correct 6 ms 1076 KB Output is correct
7 Correct 6 ms 1076 KB Output is correct
8 Correct 7 ms 1076 KB Output is correct
9 Correct 7 ms 1076 KB Output is correct
10 Correct 8 ms 1076 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 6 ms 1244 KB Output is correct
22 Correct 6 ms 1076 KB Output is correct
23 Correct 7 ms 1208 KB Output is correct
24 Correct 6 ms 1076 KB Output is correct
25 Correct 8 ms 1076 KB Output is correct
26 Correct 9 ms 1076 KB Output is correct
27 Correct 9 ms 1076 KB Output is correct
28 Correct 8 ms 1076 KB Output is correct
29 Correct 6 ms 1076 KB Output is correct
30 Correct 7 ms 1076 KB Output is correct
31 Correct 7 ms 1088 KB Output is correct
32 Correct 8 ms 1076 KB Output is correct
33 Execution timed out 2045 ms 261004 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1076 KB Output is correct
2 Correct 6 ms 1076 KB Output is correct
3 Correct 8 ms 1076 KB Output is correct
4 Correct 8 ms 1076 KB Output is correct
5 Correct 6 ms 1076 KB Output is correct
6 Correct 6 ms 1076 KB Output is correct
7 Correct 6 ms 1076 KB Output is correct
8 Correct 7 ms 1076 KB Output is correct
9 Correct 7 ms 1076 KB Output is correct
10 Correct 8 ms 1076 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 6 ms 1244 KB Output is correct
22 Correct 6 ms 1076 KB Output is correct
23 Correct 7 ms 1208 KB Output is correct
24 Correct 6 ms 1076 KB Output is correct
25 Correct 8 ms 1076 KB Output is correct
26 Correct 9 ms 1076 KB Output is correct
27 Correct 9 ms 1076 KB Output is correct
28 Correct 8 ms 1076 KB Output is correct
29 Correct 6 ms 1076 KB Output is correct
30 Correct 7 ms 1076 KB Output is correct
31 Correct 7 ms 1088 KB Output is correct
32 Correct 8 ms 1076 KB Output is correct
33 Execution timed out 2045 ms 261004 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 7 ms 1076 KB Output is correct
17 Correct 6 ms 1076 KB Output is correct
18 Correct 8 ms 1076 KB Output is correct
19 Correct 8 ms 1076 KB Output is correct
20 Correct 6 ms 1076 KB Output is correct
21 Correct 6 ms 1076 KB Output is correct
22 Correct 6 ms 1076 KB Output is correct
23 Correct 7 ms 1076 KB Output is correct
24 Correct 7 ms 1076 KB Output is correct
25 Correct 8 ms 1076 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 6 ms 1244 KB Output is correct
37 Correct 6 ms 1076 KB Output is correct
38 Correct 7 ms 1208 KB Output is correct
39 Correct 6 ms 1076 KB Output is correct
40 Correct 8 ms 1076 KB Output is correct
41 Correct 9 ms 1076 KB Output is correct
42 Correct 9 ms 1076 KB Output is correct
43 Correct 8 ms 1076 KB Output is correct
44 Correct 6 ms 1076 KB Output is correct
45 Correct 7 ms 1076 KB Output is correct
46 Correct 7 ms 1088 KB Output is correct
47 Correct 8 ms 1076 KB Output is correct
48 Execution timed out 2045 ms 261004 KB Time limit exceeded
49 Halted 0 ms 0 KB -