Submission #295574

#	Time	Username	Problem	Language	Result	Execution time	Memory
295574		RezwanArefin01	Safety (NOI18_safety)	C++17	66 / 100	2073 ms	1092 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> 
void add(T &p, int x) {
  T q; 
  while(!p.empty()) {
    q.push(p.top() + x); 
    p.pop(); 
  }
  p = q; 
}

template<class T>
void print(T p) {
  while(!p.empty()) {
    cout << p.top() << " ";
    p.pop(); 
  }
  cout << endl; 
}

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

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

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

    add(L, -h); 
    add(R, 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:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |   scanf("%d %d", &n, &h);
      |   ~~~~~^~~~~~~~~~~~~~~~~
safety.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     scanf("%d", &X);
      |     ~~~~~^~~~~~~~~~

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