Submission #295602

#	Time	Username	Problem	Language	Result	Execution time	Memory
295602		RezwanArefin01	Safety (NOI18_safety)	C++17	100 / 100	99 ms	5528 KiB

safety

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

typedef long long ll;
typedef pair<int, int> ii;

const int N = 2e5 + 5;
int n, h, X;

template <class T>
struct shift_pq {
  T Q;
  ll total;
  shift_pq() : total(0) {}

  void shift(ll X) {
    total += X;
  }
  void push(ll X) {
    Q.push(X - total);
  }
  ll top() {
    return Q.top() + total;
  }
  void pop() {
    Q.pop();
  }
};

int main() {
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d %d", &n, &h);

  shift_pq<priority_queue<ll>> L;
  shift_pq<priority_queue<ll, vector<ll>, greater<ll>>> R;

  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &X);

    L.shift(-h);
    R.shift(h);

    L.push(X);
    R.push(X);

    if (X < L.top()) {
      ans += L.top() - X;
      L.push(X);
      R.push(L.top());
      R.pop();
      L.pop();
    } else if (X > R.top()) {
      ans += X - R.top();
      R.push(X);
      L.push(R.top());
      L.pop();
      R.pop();
    }
  }

  printf("%lld\n", ans);
}

Compilation message (stderr)

safety.cpp: In function 'int main()':
safety.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   scanf("%d %d", &n, &h);
      |   ~~~~~^~~~~~~~~~~~~~~~~
safety.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     scanf("%d", &X);
      |     ~~~~~^~~~~~~~~~

• 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