oj.uz

Submission #158421

# Submission time Handle Problem Language Result Execution time Memory
158421 2019-10-17T03:01:40 Z luciocf Lightning Conductor (POI11_pio) C++14
0 / 100
 1000 ms 45572 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5+10;
const int maxl = 21;

int n;
int a[maxn];

int tab[maxn][maxl];
int lg[maxn];

void build(void)
{
	lg[1] = 0;

	for (int i = 1; i <= n; i++)
	{
		tab[i][0] = a[i];
		if (i > 2) lg[i] = lg[i/2]+1;
	}

	for (int j = 1; j < maxl; j++)
		for (int i = 1; i + (1<<j) <= n+1; i++)
			tab[i][j] = max(tab[i][j-1], tab[i+(1<<(j-1))][j-1]);
}

int mx(int l, int r)
{
	int j = lg[r-l+1];

	return max(tab[l][j], tab[r-(1<<j)+1][j]);
}

int main(void)
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	build();

	for (int i = 1; i <= n; i++)
	{
		int k = 0;

		for (int d = 1; (d-1)*(d-1) <= n; d++)
		{
			int l = max(1, i - d*d);
			int r = min(i-1, i - d*d + 2*d - 2);

			if (l > r) continue;

			k = max(k, mx(l, r) + d);
		}

		for (int d = 1; (d-1)*(d-1) <= n; d++)
		{
			int l = max(i+1, d*d - 2*d + i + 2);
			int r = min(n, i + d*d);

			if (l > r) continue;

			k = max(k, mx(l, r) + d);
		}

		printf("%d\n", max(0, k-a[i]));
	}
}

Compilation message

pio.cpp: In function 'int main()':
pio.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
pio.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 3420 KB Output isn't correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 5368 KB Output isn't correct

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 21368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 32536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 45564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 45572 KB Time limit exceeded
2 Halted 0 ms 0 KB -