Submission #851299

#	Time	Username	Problem	Language	Result	Execution time	Memory
851299		yangjl	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	179 ms	26836 KiB

bulves

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

using ll = long long;
using pii = pair<int,int>;

template< typename T >
struct SlopeTrick {
  const T INF = numeric_limits< T >::max() / 3;
  T min_f;
  priority_queue< T, vector< T >, less<> > L;
  priority_queue< T, vector< T >, greater<> > R;
  T add_l, add_r;
  T imag_l, imag_r;
private:
  void push_R(const T &a) {
    R.push(a - add_r);
  }
  T top_R() const {
    if(R.empty()) return INF;
    else return R.top() + add_r;
  }
  T pop_R() {
    T val = top_R();
    if(not R.empty()) R.pop();
    return val;
  }
  void push_L(const T &a) {
    L.push(a - add_l);
  }
  T top_L() {
    L.push(0);
    if(L.empty()) return -INF;
    else {
      return L.top() + add_l;
    }
  }
  T pop_L() {
    T val = top_L();
    if(not L.empty()) L.pop();
    return val;
  }
  size_t size() {
    return L.size() + R.size();
  }
public:
  SlopeTrick() : min_f(0), add_l(0), add_r(0), imag_l(1ll<<60), imag_r(1ll<<60) {}
  struct Query {
    T lx, rx, min_f;
  };
  // return min f(x)
  Query query() const {
    return (Query) {top_L(), top_R(), min_f};
  }
  // f(x) += a
  void add_all(const T &a) {
    min_f += a;
  }
  // add \_
  // f(x) += max(a - x, 0)
  void add_a_minus_x(const T &a) {
    min_f += max(T(0), a - top_R());
    push_R(a);
    push_L(pop_R());
  }
  // add _/
  // f(x) += max(x - a, 0)
  void add_x_minus_a(const T &a) {
    min_f += max(T(0), top_L() - a);
    push_L(a);
    push_R(pop_L());
  }
  // add \/
  // f(x) += abs(x - a)
  void add_abs(const T &a) {
    add_a_minus_x(a);
    add_x_minus_a(a);
  }
  // \/ -> \_
  // f_{new} (x) = min f(y) (y <= x)
  void clear_right() {
    while(not R.empty()) R.pop();
    imag_r = 0;
  }
  // \/ -> _/
  // f_{new} (x) = min f(y) (y >= x)
  void clear_left() {
    while(not L.empty()) L.pop();
  }
  // \/ -> \_/
  // f_{new} (x) = min f(y) (x-b <= y <= x-a)
  void shift(const T &a, const T &b) {
    assert(a <= b);
    add_l += a;
    add_r += b;
  }
  // \/. -> .\/
  // f_{new} (x) = f(x - a)
  void shift(const T &a) {
    shift(a, a);
  }
  // L, R 被破坏
  T get(const T &x) {
    T ret = min_f;
    while(not L.empty()) {
      auto val = pop_L();
      ret += max(T(0), val - x);
      if(val == add_l) break;
    }
    // while(not R.empty()) {
    //   ret += max(T(0), x - pop_R());
    // }
    return ret;
  }
  void merge(SlopeTrick &st) {
    if(st.size() > size()) {
      swap(st.L, L);
      swap(st.R, R);
      swap(st.add_l, add_l);
      swap(st.add_r, add_r);
      swap(st.min_f, min_f);
    }
    while(not st.R.empty()) {
      add_x_minus_a(st.pop_R());
    }
    while(not st.L.empty()) {
      add_a_minus_x(st.pop_L());
    }
    min_f += st.min_f;
  }

  void print(){
    cout << "L:";
    while(!L.empty()) cout << " " << pop_L(); cout << '\n';
    cout << "R:";
    while(!R.empty()) cout << " " << pop_R(); cout << '\n';
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<ll> a(n), b(n);
  for(int i = 0; i < n; i++) cin >> a[i]>> b[i];
  for(int i = 1; i < n; i++) a[i] += a[i - 1];
  SlopeTrick<ll> pq;
  for(int i = 0; i < n; i++){
    pq.shift(b[i]);
    pq.clear_right();
    pq.add_abs(a[i]);
  }
  cout << pq.get(a[n - 1]) << '\n';
  return 0;
}

Compilation message (stderr)

bulves.cpp: In member function 'void SlopeTrick<T>::print()':
bulves.cpp:134:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  134 |     while(!L.empty()) cout << " " << pop_L(); cout << '\n';
      |     ^~~~~
bulves.cpp:134:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  134 |     while(!L.empty()) cout << " " << pop_L(); cout << '\n';
      |                                               ^~~~
bulves.cpp:136:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  136 |     while(!R.empty()) cout << " " << pop_R(); cout << '\n';
      |     ^~~~~
bulves.cpp:136:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  136 |     while(!R.empty()) cout << " " << pop_R(); cout << '\n';
      |                                               ^~~~

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36