Submission #282811

#	Time	Username	Problem	Language	Result	Execution time	Memory
282811		rama_pang	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1415 ms	67740 KiB

bulldozer

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

using lint = long long;

struct Node {
  lint l = 0;
  lint r = 0;
  lint mx = 0;
  lint sum = 0;
  Node() {}
  Node(lint v) {
    l = r = mx = max(v, 0ll);
    sum = v;
  }
  Node(lint l, lint r, lint mx) : l(l), r(r), mx(mx) {}
};

Node Merge(const Node &a, const Node &b) {
  Node res;
  res.sum = a.sum + b.sum;
  res.l = max(a.l, a.sum + b.l);
  res.r = max(b.r, b.sum + a.r);
  res.mx = max({a.mx, b.mx, a.r + b.l});
  return res;
}

class SegTree {
 public:
  int sz;
  vector<Node> tree;

  SegTree() {}
  SegTree(int n) {
    sz = 1;
    while (sz < n) sz *= 2;
    tree.resize(2 * sz);
  }

  void Modify(int p, int x) {
    tree[p += sz] = Node(x);
    for (p /= 2; p > 0; p /= 2) {
      tree[p] = Merge(tree[p * 2], tree[p * 2 + 1]);
    }
  }

  lint Query() {
    return tree[1].mx;
  }
};

class DisjointSet {
 public:
  int sz;
  vector<int> p;
  vector<int> hist;

  DisjointSet() {}
  DisjointSet(int sz) : sz(sz), p(sz) {
    iota(begin(p), end(p), 0);
  } 

  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }

  int Unite(int x, int y) {
    hist.emplace_back(x);
    hist.emplace_back(y);
    x = Find(x), y = Find(y);
    if (x == y) return 0;
    p[x] = y;
    return 1;
  }

  void Clear() {
    for (auto i : hist) {
      p[i] = i;
    }
    hist.clear();
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N;
  cin >> N;
  vector<int> X(N), Y(N), V(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i] >> V[i];
  }
  
  vector<pair<pair<int, int>, pair<int, int>>> all;
  auto Add = [&](int p, int q) {
    int x = X[p] - X[q];
    int y = Y[p] - Y[q];
    if (x == 0) {
      y = 1;
    } else if (y == 0) {
      x = 1;
    } else {
      if (y < 0) {
        x *= -1;
        y *= -1;
      }
      int g = __gcd(abs(x), abs(y));
      x /= g;
      y /= g;
    }
    all.push_back({{x, y}, {p, q}});
  };

  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      Add(i, j);
    }
  }

  auto angcmp = [&](pair<int, int> a, pair<int, int> b) {
    return 1ll * a.first * b.second - 1ll * a.second * b.first > 0;
  };
  sort(begin(all), end(all), [&](const pair<pair<int, int>, pair<int, int>> a, 
                                 const pair<pair<int, int>, pair<int, int>> b) {
    return angcmp(a.first, b.first);
  });

  vector<int> ord(N);
  iota(begin(ord), end(ord), 0);
  sort(begin(ord), end(ord), [&](int i, int j) {
    return Y[i] < Y[j] || (Y[i] == Y[j] && X[i] < X[j]);
  });
  vector<int> pos(N);
  for (int i = 0; i < N; i++) {
    pos[ord[i]] = i;
  }

  SegTree seg(N);
  for (int i = 0; i < N; i++) {
    seg.Modify(i, V[ord[i]]);
  }
  lint ans = seg.Query();

  for (int f = 0; f < (int) all.size(); f++) {
    int until = f;
    while (until + 1 < (int) all.size() && all[until + 1].first == all[f].first) {
      until++;
    }
    static vector<pair<int, int>> v; 
    v.clear();
    for (int i = f; i <= until; i++) {
      v.emplace_back(all[i].second);
    }
    f = until;
    
    static DisjointSet D(N);
    static vector<pair<int, int>> swaps;
    static vector<int> elems;
    D.Clear(); swaps.clear(); elems.clear();
    for (auto i : v) {
      D.Unite(i.first, i.second);
      elems.emplace_back(i.first);
      elems.emplace_back(i.second);
    }
    sort(begin(elems), end(elems));
    elems.resize(unique(begin(elems), end(elems)) - begin(elems));

    sort(begin(elems), end(elems), [&](int i, int j) {
      if (D.Find(i) != D.Find(j)) return D.Find(i) < D.Find(j);
      return Y[i] < Y[j] || (Y[i] == Y[j] && X[i] < X[j]);
    });

    for (int i = 0; i < (int) elems.size(); i++) {
      int j = i;
      while (j + 1 < (int) elems.size() && D.Find(elems[j + 1]) == D.Find(elems[i])) {
        j++;
      }
      for (int k = i; k <= j; k++) {
        int other = j - (k - i);
        if (k < other) {
          swaps.emplace_back(elems[k], elems[other]);
        }
      }
      i = j;
    }

    for (auto i : swaps) {
      swap(pos[i.first], pos[i.second]);
      swap(ord[pos[i.first]], ord[pos[i.second]]);
      seg.Modify(pos[i.first], V[i.first]);
      seg.Modify(pos[i.second], V[i.second]);
    }
    ans = max(ans, seg.Query());
  }

  cout << ans << "\n";
  return 0;
}

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