Submission #1280754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280754		Pannda	Bulldozer (JOI17_bulldozer)	C++20	0 / 100	2 ms	840 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;

template<class Info>
struct SegmentTree {
    int n;
    vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        std::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 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;
        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;
        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);
    }
    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;
        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;
        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 Info {
    long long mx = 0;
    long long pre = 0;
    long long suf = 0;
    long long sum = 0;
    Info() {}
    Info(int x) {
        sum = x;
        mx = pre = suf = max(0, x);
    }
    Info operator+(const Info &b) {
        Info ret;
        ret.mx = max({mx, b.mx, suf + b.pre});
        ret.pre = max(pre, sum + b.pre);
        ret.suf = max(b.suf, b.sum + suf);
        ret.sum = sum + b.sum;
        return ret;
    }
};

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct point {
    int x, y, w;
    bool operator<(const point &other) const {
        return tie(x, y) < tie(other.x, other.y);
    }
};

struct Line{
  ll i, j, dx, dy; // dx >= 0
  Line(int i, int j, const point &pi, const point &pj)
    : i(i), j(j), dx(pj.x-pi.x), dy(pj.y-pi.y) {}
  bool operator < (const Line &l) const {
    return make_tuple(dy*l.dx, i, j) < make_tuple(l.dy*dx, l.i, l.j); }
  bool operator == (const Line &l) const {
    return dy * l.dx == l.dy * dx; }
};

void Bulldozer(vector<point> a, auto &&swapcb, auto &&updatecb){ // V.reserve(N*(N-1)/2)
  int n = a.size();
  vector<int> p(n);
  sort(a.begin(), a.end()); iota(p.begin(), p.end(), 0); vector<Line> v;
  for(int i=0; i<n; i++) for(int j=i+1; j<n; j++)
    v.emplace_back(i, j, a[i], a[j]);
  sort(v.begin(), v.end());
  for(int i=0, j=0; i<v.size(); i=j){
    while(j < v.size() && v[i] == v[j]) j++;
    for(int k=i; k<j; k++){
      int x = v[k].i, y = v[k].j; // point id, index -> Pos[id]
      swapcb(p[x], p[y]); swap(p[x], p[y]);
    }
    updatecb();
  }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    map<array<int, 2>, long long> mp;
    for (int i = 0; i < n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        mp[{x, y}] += w;
    }

    vector<point> a;
    for (auto [xy, w] : mp) {
        auto [x, y] = xy;
        a.push_back({x, y, w});
    }
    n = a.size();

    vector<int> v;
    for (auto [x, y, w] : a) {
        v.push_back(w);
    }

    SegmentTree<Info> seg(v);
    long long ans = 0;

    Bulldozer(a, [&](int i, int j) {
        int x = v[i];
        int y = v[j];
        seg.modify(i, y);
        seg.modify(j, x);
        swap(v[i], v[j]);
    }, [&]() {
        ans = max(ans, seg.rangeQuery(0, n).mx);
    });

    cout << ans << '\n';

}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:190:28: warning: narrowing conversion of 'w' from 'std::tuple_element<1, std::pair<const std::array<int, 2>, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  190 |         a.push_back({x, y, w});
      |                            ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20