Submission #72126

#	Time	Username	Problem	Language	Result	Execution time	Memory
72126		동진의 (#118)	Box Run (FXCUP3_box)	C++17	100 / 100	497 ms	9500 KiB

box

#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 (stderr)

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 / 17
• Subtask 2: 83 / 83