Submission #551750

#	Time	Username	Problem	Language	Result	Execution time	Memory
551750		cadmiumsky	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1756 ms	2752 KiB

bulldozer

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx")
//#define int long long
using namespace std;
using ll = long long;
const int nmax = 2e3 + 5;
int n;

vector< tuple<int,int,ll> > points;
vector<int> ind;

namespace SSM {
  #define int ll
  struct Node {
    int sum, pref, suff, mx;
    Node() : sum(0), pref(0), suff(0), mx(0) {;}
    Node(int val) : sum(val), pref(max(0LL, val)), suff(max(0LL, val)), mx(max(0LL, val)) {;}
    Node(int s, int p, int u, int m) : sum(s), pref(p), suff(u), mx(m) {;}
    Node operator +(const Node& x) const {
      return Node(x.sum + sum, 
                  max(pref, sum + x.pref), 
                  max(x.suff, x.sum + suff), 
                  max({mx, x.mx, suff + x.pref}));
    }
  };
  #undef int
  Node aint[nmax * 4];
  void upd(int poz, ll val, int node = 1, int cl = 0, int cr = n - 1) {
    if(cl == cr) {
      aint[node] = val;
      return;
    }
    int mid = cl + cr >> 1;
    if(poz <= mid)
      upd(poz, val, 2 * node, cl, mid);
    else
      upd(poz, val, 2 * node + 1, mid + 1, cr);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
  void construct(int l, int r, bool state = 0, int node = 1, int cl = 0, int cr = n - 1) {
  int mid = cl + cr >> 1;
    switch(state) {
      case 0:
        if(l <= cl && cr <= r) {
          construct(l, r, 1, node, cl, cr);
          return;
        }
        if(r < cl || cr < l)
          return;
        construct(l, r, 0, 2 * node, cl, mid);
        construct(l, r, 0, 2 * node + 1, mid + 1, cr);
        aint[node] = aint[2 * node] + aint[2 * node + 1];
        break;
      case 1:
        if(cl == cr) {
          aint[node] = get<2>(points[ind[cl]]);
          return;
        }
        construct(l, r, 1, 2 * node, cl, mid);
        construct(l, r, 1, 2 * node + 1, mid + 1, cr);
        aint[node] = aint[2 * node] + aint[2 * node + 1];
        break;
    };
  }
  ll query() { return aint[1].mx; }
};
#define int ll 
namespace LineContainer { // catthink
  pair<ll,ll> getline(int l, int r) { return {-(get<1>(points[l]) - get<1>(points[r])), -(get<0>(points[l]) - get<0>(points[r]))};}; 
  bool cmpline(pair<ll,ll> l, pair<ll,ll> r) { return (ll)l.first * r.second > (ll)r.first * l.second;};
  bool eqline(pair<ll,ll> l, pair<ll,ll> r) { return (ll)l.first * r.second == (ll)r.first * l.second; };
  bool eq(int i, int j) { return eqline(getline(ind[i], ind[i + 1]), getline(ind[j], ind[j + 1])); };
  auto cmp = [](int i, int j) { return cmpline(getline(ind[i], ind[i + 1]), getline(ind[j], ind[j + 1]))
                                        || (eq(i, j) && i < j); };
  set<int, decltype(cmp)> heap(cmp);
  void rev(int l, int r) {
    if(r - l > 1)
      cerr << "Reverse: " << l << ' ' << r << '\n';
    if(l > 0 && ind[l - 1] < ind[l])
      heap.erase(l - 1);
    if(r < ind.size() - 1 && ind[r] < ind[r + 1])
      heap.erase(r);
    reverse(ind.begin() + l, ind.begin() + r + 1);
    if(l > 0 && ind[l - 1] < ind[l])
      heap.insert(l - 1);
    if(r < ind.size() - 1 && ind[r] < ind[r + 1])
      heap.insert(r);
    SSM::construct(l, r);
  }
  int startmove() {
    if(heap.size() == 0)
      return -1;
    int u = *heap.begin(), last = u;
    //cerr << "- " << u << '\n';
    heap.erase(heap.begin());
    while(!heap.empty() && eq(*heap.begin(), u)) {
      if(*heap.begin() - u > 1) {
        rev(last, u + 1);
        last = *heap.begin();
      }
      u = *heap.begin();
      heap.erase(heap.begin());
    }
    rev(last, u + 1);
    return SSM::query();
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  points.resize(n);
  ind.resize(n);
  for(auto &[a, b, c] : points)
    cin >> a >> b >> c;
  sort(points.begin(), points.end());
  for(int i = 0; i < n; i++)
    //cerr << get<0>(points[i]) << ' ' << get<1>(points[i]) << '\n', 
    SSM::upd(i, get<2>(points[i])),
    ind[i] = i;
  for(int i = 0; i < n - 1; i++)
    LineContainer::heap.insert(i);
  ll mx = SSM::query(), temp;
  while((temp = LineContainer::startmove()) >= 0) {
    mx = max(mx, temp);
  }
  cout << mx << '\n';
}

Compilation message (stderr)

bulldozer.cpp: In function 'void SSM::upd(int, ll, int, int, int)':
bulldozer.cpp:34:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
bulldozer.cpp: In function 'void SSM::construct(int, int, bool, int, int, int)':
bulldozer.cpp:42:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
bulldozer.cpp: In function 'void LineContainer::rev(ll, ll)':
bulldozer.cpp:82:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     if(r < ind.size() - 1 && ind[r] < ind[r + 1])
      |        ~~^~~~~~~~~~~~~~~~
bulldozer.cpp:87:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     if(r < ind.size() - 1 && ind[r] < ind[r + 1])
      |        ~~^~~~~~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:115:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |   for(auto &[a, b, c] : points)
      |             ^

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