Submission #707748

#	Time	Username	Problem	Language	Result	Execution time	Memory
707748		pauloamed	Safety (NOI18_safety)	C++14	100 / 100	140 ms	7008 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 SlopeTrick{
  int a, b; // ax + b
  SlopeTrick(int _a, int _b):a(_a), b(_b){}

  OffsetPq<less<int>> slopeChangeUntil0;
  OffsetPq<greater<int>> slopeChangeAfter0;
  
  void merge(SlopeTrick &st){
    a += st.a, b += st.b;

    auto addToPQs = [&](int x) {
      if(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();
    }

    // print();

    while(abs(a) > slopeChangeUntil0.size()) {
      int x = slopeChangeAfter0.top();
      slopeChangeAfter0.pop();
      slopeChangeUntil0.push(x);
    }

    while(abs(a) < slopeChangeUntil0.size()) {
      int x = slopeChangeUntil0.top();
      slopeChangeUntil0.pop();
      slopeChangeAfter0.push(x);
    }
  }

  void min_op(int h){
    b += h * a;
    slopeChangeAfter0.addToOffset(h);
    slopeChangeUntil0.addToOffset(-h);
  }

  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";
  }
};


SlopeTrick buildAbs(int a){
  // builds |a - x|
  SlopeTrick 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;

  SlopeTrick dp = buildAbs(v[0]);
  // dp.print();

  for(int i = 1; i < n; ++i){
    // dp is f
    dp.min_op(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 SlopeTrick::merge(SlopeTrick&)':
safety.cpp:52:18: 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]
   52 |     while(abs(a) > slopeChangeUntil0.size()) {
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:58:18: 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]
   58 |     while(abs(a) < slopeChangeUntil0.size()) {
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp: In member function 'void SlopeTrick::print()':
safety.cpp:80:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   80 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
safety.cpp:80:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |       for(auto y : v) cout << y << " "; cout << endl;
      |                                         ^~~~
safety.cpp:88:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   88 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
safety.cpp:88:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   88 |       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