oj.uz

Submission #72126

# Submission time Handle Problem Language Result Execution time Memory
72126 2018-08-26T05:25:29 Z 동진의 (#2167, kdk3776, define_chan, Jinpari) Box Run (FXCUP3_box) C++17
100 / 100
 497 ms 9500 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;

struct segment_tree
{
	int tree_max[2000005];

	void update(int i, int value, int node, int start, int end)
	{
		if (i < start || end < i)
			return;
		else if (start == end)
		{
			tree_max[node] = value;
		}
		else
		{
			int mid = start + end >> 1;
			update(i, value, node * 2, start, mid);
			update(i, value, node * 2 + 1, mid + 1, end);
			tree_max[node] = max(tree_max[node * 2], tree_max[node * 2 + 1]);
		}
	}

	int maxValue(int l, int r, int node, int start, int end)
	{
		if (r < start || end < l)
			return 0;
		else if (l <= start && end <= r)
			return tree_max[node];
		else
		{
			int mid = start + end >> 1;
			return max(maxValue(l, r, node * 2, start, mid), maxValue(l, r, node * 2 + 1, mid + 1, end));
		}
	}
};

segment_tree st;
int h[500005];

int main()
{
	int n;

	scanf(" %d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf(" %d", h + i);
		st.update(i, h[i], 1, 1, n);
	}


	int x = 1;
	for (int i = 1; i <= n; i++)
	{
		while (x < n)
		{
			if (x - i + 1 >= 1 && h[x + 1] > st.maxValue(x - i + 1, x, 1, 1, n))
			{
				printf("%d ", x - i + 1);
				break;
			}
			x++;
		}
		if (x >= n)
			printf("-1 ");
	}
	printf("\n");
	return 0;
}

Compilation message

box.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
box.cpp:19:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = start + end >> 1;
              ~~~~~~^~~~~
box.cpp: In member function 'int segment_tree::maxValue(int, int, int, int, int)':
box.cpp:34:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = start + end >> 1;
              ~~~~~~^~~~~
box.cpp: In function 'int main()':
box.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d", &n);
  ~~~~~^~~~~~~~~~~
box.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d", h + i);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct

Subtask #2
83.0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 4 ms 548 KB Output is correct
14 Correct 36 ms 1420 KB Output is correct
15 Correct 68 ms 2240 KB Output is correct
16 Correct 89 ms 2520 KB Output is correct
17 Correct 266 ms 5156 KB Output is correct
18 Correct 328 ms 7708 KB Output is correct
19 Correct 428 ms 8732 KB Output is correct
20 Correct 497 ms 9500 KB Output is correct
21 Correct 460 ms 9500 KB Output is correct