Submission #709503

#	Time	Username	Problem	Language	Result	Execution time	Memory
709503		pauloamed	Safety (NOI18_safety)	C++14	100 / 100	141 ms	7000 KiB

safety

#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() {
    a = min(a, 0LL);
    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 << "PRINT: \n";
    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, h; cin >> n >> h;
  vector<int> v(n); for(auto &x : v) cin >> x;
 
  PiecewiseConvex dp = buildAbs(v[0]);
  // dp.print();
 
  for(int i = 1; i < n; ++i){
    // dp is f
    dp.min_op(h, h);
    // dp.print();
    
    // dp is g
    auto x = buildAbs(v[i]);
    dp.merge(x);
    // dp.print();
  }
 
  int sum_b = 0;
  while(dp.slopeChangeUntil0.size()) {
    sum_b += dp.slopeChangeUntil0.top();
    dp.slopeChangeUntil0.pop();
  }
 
  cout << dp.b - sum_b << "\n";
}

Compilation message (stderr)

safety.cpp: In member function 'void PiecewiseConvex::merge(PiecewiseConvex&)':
safety.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()) {
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
safety.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()) {
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp: In member function 'void PiecewiseConvex::print()':
safety.cpp:97:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   97 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
safety.cpp:97:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   97 |       for(auto y : v) cout << y << " "; cout << endl;
      |                                         ^~~~
safety.cpp:105:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  105 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
safety.cpp:105:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  105 |       for(auto y : v) cout << y << " "; cout << endl;
      |                                         ^~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29