Submission #707955

#	Time	Username	Problem	Language	Result	Execution time	Memory
707955		pauloamed	Potatoes and fertilizers (LMIO19_bulves)	C++14	24 / 100	366 ms	26908 KiB

bulves

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define mp make_pair
 
template<typename T> struct OffsetPq : 
  priority_queue<int,vector<int>,T> {
  int offset = 0;
 
  void push(int x) {
    priority_queue<int,vector<int>, T>::push(x - offset);
  }
 
  int top() {
    return priority_queue<int,vector<int>,T>::top() + offset;
  }
 
  void addToOffset(int x) {
    offset += x;
  }
};
 
struct PiecewiseConvex{
  int a, b; // ax + b
  OffsetPq<less<int>> slopeChangeUntil0;
  OffsetPq<greater<int>> slopeChangeAfter0;
 
  PiecewiseConvex(int _a=0, int _b=0):a(_a), b(_b){}
  
  void merge(PiecewiseConvex &st){
    a += st.a, b += st.b;
 
    auto addToPQs = [&](int x) {
      if(slopeChangeAfter0.size() && slopeChangeAfter0.top() <= x)
        slopeChangeAfter0.push(x);
      else slopeChangeUntil0.push(x);
    };
 
    while(st.slopeChangeUntil0.size()) {
      addToPQs(st.slopeChangeUntil0.top());
      st.slopeChangeUntil0.pop();
    }
    
    while(st.slopeChangeAfter0.size()) {
      addToPQs(st.slopeChangeAfter0.top());
      st.slopeChangeAfter0.pop();
    }
 
    if(a < 0) {
      while(-a > slopeChangeUntil0.size()) {
        int x = slopeChangeAfter0.top();
        slopeChangeAfter0.pop();
        slopeChangeUntil0.push(x);
      }
  
      while(-a < slopeChangeUntil0.size()) {
        int x = slopeChangeUntil0.top();
        slopeChangeUntil0.pop();
        slopeChangeAfter0.push(x);
      }
    } else if(a >= 0) {
      while(slopeChangeUntil0.size()) {
        int x = slopeChangeUntil0.top();
        slopeChangeUntil0.pop();
        slopeChangeAfter0.push(x);
      }
    }

  }

  void min_pref() {
    slopeChangeAfter0 = OffsetPq<greater<int>>();
  }
 
  void min_op(int h0, int h1) {
    // f(x) = g(t), t - x <= h0, x - t <= h1
    b += h0 * a;
    slopeChangeUntil0.addToOffset(-h0);
    slopeChangeAfter0.addToOffset(h1);
  }
 
  void print(){
    cout << a << " " << b << "\n";
    {
      auto x = slopeChangeUntil0;
      vector<int> v;
      while(x.size()) {
        v.push_back(x.top()); x.pop();
      }
      reverse(v.begin(), v.end());
      for(auto y : v) cout << y << " "; cout << endl;
    }
    {
      auto x = slopeChangeAfter0;
      vector<int> v;
      while(x.size()) {
        v.push_back(x.top()); x.pop();
      }
      for(auto y : v) cout << y << " "; cout << endl;
    }
    cout << "------------------------\n";
  }
};
 
 
PiecewiseConvex buildAbs(int a){
  // builds |a - x|
  PiecewiseConvex st(-1, a);
  st.slopeChangeUntil0.push(a);
  st.slopeChangeAfter0.push(a);
  return st;
}
 
int32_t main(){
  int n; cin >> n;
  vector<int> a(n), b(n);
  for(int i = 0; i < n; ++i) cin >> a[i] >> b[i];

  vector<int> dif;
  for(int i = 0; i < n; ++i)
    dif.push_back(a[i] - b[i]);
  
  vector<int> d = {0};
  for(int i = 0; i < n; ++i) {
    d.push_back(dif[i] + d.back());
  }

  // for(auto x : d) cout << x << " ";
  // cout << endl;

  // turn d into non-dec
  
  PiecewiseConvex dp = buildAbs(d[0]);
  dp.min_pref();
  for(int i = 1; i < d.size(); ++i) {
    // cout << "processing " << i << ": " << d[i] << endl;

    PiecewiseConvex transition;
    if(d[i] < d[0]) {
      transition = PiecewiseConvex(1, -d[i]);
    } else {
      transition = buildAbs(d[i]);
    }

    dp.merge(transition);
    dp.min_pref();

    // dp.print();
  }

  // cout << d.back() << "\n";

  int sum_b = 0;
  while(dp.slopeChangeUntil0.size()) {
    int pt = dp.slopeChangeUntil0.top();
    dp.slopeChangeUntil0.pop();

    if(pt <= d.back()) sum_b += pt;
  }
 
  cout << dp.b - sum_b << "\n";
}

Compilation message (stderr)

bulves.cpp: In member function 'void PiecewiseConvex::merge(PiecewiseConvex&)':
bulves.cpp:51:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::priority_queue<long long int, std::vector<long long int>, std::less<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |       while(-a > slopeChangeUntil0.size()) {
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bulves.cpp:57:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::priority_queue<long long int, std::vector<long long int>, std::less<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |       while(-a < slopeChangeUntil0.size()) {
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bulves.cpp: In member function 'void PiecewiseConvex::print()':
bulves.cpp:92:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   92 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
bulves.cpp:92:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   92 |       for(auto y : v) cout << y << " "; cout << endl;
      |                                         ^~~~
bulves.cpp:100:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  100 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
bulves.cpp:100:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  100 |       for(auto y : v) cout << y << " "; cout << endl;
      |                                         ^~~~
bulves.cpp: In function 'int32_t main()':
bulves.cpp:136:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   for(int i = 1; i < d.size(); ++i) {
      |                  ~~^~~~~~~~~~

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