Submission #467684

#	Time	Username	Problem	Language	Result	Execution time	Memory
467684		thaixuandang	Safety (NOI18_safety)	C++17	100 / 100	138 ms	5512 KiB

safety

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifndef LOCAL
#define debug(...) (void)0
#endif

using namespace std;

namespace __gnu_pbds {
  template<typename T>
  using ordered_set = tree<
    T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
}

using __gnu_pbds::ordered_set;
using int128 = __int128;

template<typename T>
bool maximize(T& target, const T& value) 
{ return target < value ? (target = value, true) : false; }

template<typename T>
bool minimize(T& target, const T& value)
{ return target > value ? (target = value, true) : false; }

istream& operator>>(istream& is, int128& x)
{ long long y; is >> y, x = y; return is; }

ostream& operator<<(ostream& os, const int128& x) 
{ assert(x >= LONG_LONG_MIN && x <= LONG_LONG_MAX); return os << (long long)x; }

const int inf = 0x3f3f3f3f;
const long long linf = 0x3f3f3f3f3f3f3f3f;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int main() {
  int n, h;
  cin >> n >> h;
  priority_queue<long long> left;
  priority_queue<long long, vector<long long>, greater<long long>> right;
  long long dl = 0, dr = 0;
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    if (i == 0) {
      left.push(a);
      right.push(a);
      continue;
    }
    dl -= h, dr += h;
    if (a < left.top() + dl) {
      ans += left.top() + dl - a;
      left.push(a - dl);
      left.push(a - dl);
      right.push(left.top() + dl - dr);
      left.pop();
    } else if (a > right.top() + dr) {
      ans += a - (right.top() + dr);
      right.push(a - dr);
      right.push(a - dr);
      left.push(right.top() + dr - dl);
      right.pop();
    } else {
      left.push(a - dl);
      right.push(a - dr);
    }
  }
  cout << ans << '\n';
  return 0;
}

• 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