oj.uz

답안 #1117763

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117763 2024-11-24T08:10:08 Z Pannda Bulldozer (JOI17_bulldozer) C++17
0 / 100
 3 ms 848 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;
    }
};

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<array<int, 2>> crit_list = [&] { // Gives a list of critical points in [-pi/2,pi/2) in order, expressed by (i, j) : before the critical point i<j and after that i>j. When exactly are the critical points are not returned
        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<array<int, 2>> res;
        for (int i = 0; i < fetch.size(); i++) {
            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) {
//
//            });
            for (int ii = 0; ii + 1 < ids.size(); ii++) {
                res.push_back({ids[ii], ids[ii + 1]});
            }
        }
        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][1];
    });
    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 [i, j] : crit_list) {
        if (ip[i] > ip[j]) swap(i, j);
        assert(ip[i] - ip[j] == -1);

        seg.modify(ip[i], Info(w[j]));
        seg.modify(ip[j], Info(w[i]));
        ans = max(ans, seg.rangeQuery(0, n).allmax);

        swap(p[ip[i]], p[ip[j]]);
        swap(ip[i], ip[j]);
    }

    cout << ans << '\n';
}

Compilation message

bulldozer.cpp: In lambda function:
bulldozer.cpp:243: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]
  243 |         for (int i = 0; i < fetch.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
bulldozer.cpp:258:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |             for (int ii = 0; ii + 1 < ids.size(); ii++) {
      |                              ~~~~~~~^~~~~~~~~~~~
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:241:10:   required from here
bulldozer.cpp:236:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  236 |             auto [i0, j0] = ij0;
      |                  ^~~~~~~~
bulldozer.cpp:238:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  238 |             auto [i1, j1] = ij1;
      |                  ^~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 832 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 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 512 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 3 ms 592 KB Output is correct
24 Runtime error 2 ms 720 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 832 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 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 512 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 3 ms 592 KB Output is correct
24 Runtime error 2 ms 720 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 832 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 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 512 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 3 ms 592 KB Output is correct
24 Runtime error 2 ms 720 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -