Submission #26611

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26611	2017-07-03T12:49:55 Z	model_code	Lightning Conductor (POI11_pio)	C++11	100 / 100	196 ms	8948 KB

pio

/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Piorunochron                                     *
 *   Autor:             Jakub Pachocki                                   *
 *   Zlozonosc czasowa: O(n)                                             *
 *   Opis:              Rozwiazanie wzorcowe                             *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <cmath>
#include <cassert>
#include <algorithm>

using namespace std;

const int N = (int) 5e5;
const int sN = 720;

double sqt[N + 1];

int h[N + 1], hMax;

int n;

int findL(int a, int b) {
	int l = b, r = n + 1;
	while (l < r) {
		int c = (l + r) / 2;
		if (h[a] + sqt[abs(a - c)] >= h[b] + sqt[abs(b - c)])
			l = c + 1;
		else
			r = c;
	}
	return l;
}

int s[sN + 1], l[sN + 1], ss;

int res[N + 1];

void find() {
	ss = 0;
  s[0] = 0;
  h[0] = -1e6;
	int prev = hMax - (int) ceil(sqt[n]) - 1;
	for (int i = 1; i <= n; ++i) {
		if (h[i] > prev) {
			prev = h[i];
			while (ss >= 1 && findL(s[ss], i) <= l[ss])
				--ss;
			l[ss + 1] = findL(s[ss], i);
			if (l[ss + 1] <= n)
				s[++ss] = i;
		}
	}
	int r = n;
	for (int i = ss; i >= 1; --i) {
		while (r >= l[i]) {
			res[r] = max(res[r], h[s[i]] - h[r] + (int) ceil(sqt[abs(s[i] - r)]));
			--r;
		}
	}
}

int main() {
	assert(scanf("%d", &n));
	hMax = 0;
	for (int i = 1; i <= n; ++i) {
		assert(scanf("%d", &h[i]));
		hMax = max(hMax, h[i]);
	}
	for (int i = 0; i <= n; ++i)
		sqt[i] = sqrt(i);
	find();
	reverse(h + 1, h + n + 1);
	reverse(res + 1, res + n + 1);
	find();
	reverse(res + 1, res + n + 1);
	for (int i = 1; i <= n; ++i)
		printf("%d\n", res[i]);
}

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	8948 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	8948 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	8948 KB	Output is correct

Subtask #4

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8948 KB	Output is correct

Subtask #5

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	8948 KB	Output is correct

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	8948 KB	Output is correct
2	Correct	9 ms	8948 KB	Output is correct
3	Correct	33 ms	8948 KB	Output is correct

Subtask #7

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	8948 KB	Output is correct
2	Correct	43 ms	8948 KB	Output is correct
3	Correct	23 ms	8948 KB	Output is correct

Subtask #8

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	8948 KB	Output is correct
2	Correct	66 ms	8948 KB	Output is correct
3	Correct	93 ms	8948 KB	Output is correct

Subtask #9

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	8948 KB	Output is correct
2	Correct	126 ms	8948 KB	Output is correct
3	Correct	106 ms	8948 KB	Output is correct

Subtask #10

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	126 ms	8948 KB	Output is correct
2	Correct	196 ms	8948 KB	Output is correct
3	Correct	139 ms	8948 KB	Output is correct

Subtask #11

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	186 ms	8948 KB	Output is correct
2	Correct	119 ms	8948 KB	Output is correct
3	Correct	133 ms	8948 KB	Output is correct