Submission #141102

#	Time	Username	Problem	Language	Result	Execution time	Memory
141102		tincamatei	Safety (NOI18_safety)	C++14	100 / 100	76 ms	3684 KiB

safety

#include <bits/stdc++.h>

const int MAX_N = 200000;

using namespace std;

struct Hull {
	int sign;
	priority_queue<long long> pq;
	long long lazy;

	Hull(int x):sign(x) {
		lazy = 0LL;
	}

	void insert(long long x) {
		pq.push((x - lazy) * sign);
	}

	void erase() {
		pq.pop();
	}

	long long top() {
		return max(0LL, pq.top() * sign + lazy);
	}

	void add(long long val) {
		lazy += val;
	}
} leftHull(1), rightHull(-1);

int main() {
	int N, x, H;
	long long rez = 0LL;

	scanf("%d%d", &N, &H);
	scanf("%d", &x);

	leftHull.insert(x);
	rightHull.insert(x);

	for(int i = 1; i < N; ++i) {
		scanf("%d", &x);

		leftHull.add(-H);
		rightHull.add(H);

		if(leftHull.top() <= x && x <= rightHull.top()) {
			leftHull.insert(x);
			rightHull.insert(x);
		} else if(x >= rightHull.top()) {
			rightHull.insert(x);
			rightHull.insert(x);
			leftHull.insert(rightHull.top());
			rightHull.erase();

			rez = rez + x - leftHull.top();
		} else {
			leftHull.insert(x);
			leftHull.insert(x);
			rightHull.insert(leftHull.top());
			leftHull.erase();

			rez = rez + rightHull.top() - x;
		}
	}

	printf("%lld", rez);
	return 0;
}

Compilation message (stderr)

safety.cpp: In function 'int main()':
safety.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &H);
  ~~~~~^~~~~~~~~~~~~~~~
safety.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &x);
  ~~~~~^~~~~~~~~~
safety.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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