oj.uz

Submission #141099

# Submission time Handle Problem Language Result Execution time Memory
141099 2019-08-06T17:40:44 Z tincamatei Safety (NOI18_safety) C++14
0 / 100
 52 ms 3580 KB 
#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 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 + rightHull.top() - leftHull.top();
		} else {
			leftHull.insert(x);
			leftHull.insert(x);
			rightHull.insert(leftHull.top());
			leftHull.erase();

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

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

Compilation message

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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 3580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -