Submission #72502

#	Time	Username	Problem	Language	Result	Execution time	Memory
72502		Semteo For Ajou (#118)	Box Run (FXCUP3_box)	C++17	0 / 100	3 ms	484 KiB

box

#include <stdio.h>
int ans[500005], arr[500005];
int it[1100000];
int maxi, t=1;
void max_it(int ns, int ne, int s, int e, int now) {
	if (e < ns || ne < s) return;
	if (ns <= s && e <= ne) {
		if (maxi < it[now]) maxi = it[now];
		return;
	}
	max_it(ns, ne, s, (s + e) / 2, now * 2);
	max_it(ns, ne, (s + e) / 2 + 1, e, now * 2 + 1);
}
int fd(int s, int e, int val)
{
	int left, right;
	while (s!=e) {
		//printf("1\n");
		maxi = 0;
		max_it(s, (s + e) / 2, 1, t, 1);
		left = maxi;
		if (val < left) e = (s + e) / 2;
		else {
			s = (s + e) / 2 + 1;
		}
	}
	return s;
}
int main()
{
	int n, i, j, p, now, next, flag=0;
	scanf("%d", &n);
	while (1) {
		if (t > n) break;
		t = t * 2;
	}
	for (i = t; i < t+n; i++) {
		scanf("%d", &it[i]);
		p = i / 2;
		while (p > 0) {
			if (it[p] < it[i]) it[p] = it[i];
			p = p / 2;
		}
	}
	for (i = 1; i <= n; i++) {
		//printf("%d\n", i);
		if (flag == 1 || i == n) {
			ans[i] = -1;
			continue;
		}
		maxi = 0;
		max_it(1, i, 1, t, 1);
		now = maxi;
		for (j = i + 1; j <= n; j = j + i) {
			maxi = 0;
			max_it(j, j + i - 1, 1, t, 1);
			next = maxi;
			//printf("%d %d\n", now, next);
			if (now < next) {
				ans[i]=fd(j, j + i - 1, now)-i;
				break;
			}
			now = next;
		}
		if (j > n) {
			ans[i] = -1;
			flag = 1;
		}
	}
	for (i = 1; i <= n; i++) printf("%d ", ans[i]);
	return 0;
}

Compilation message (stderr)

box.cpp: In function 'int fd(int, int, int)':
box.cpp:16:12: warning: unused variable 'right' [-Wunused-variable]
  int left, right;
            ^~~~~
box.cpp: In function 'int main()':
box.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
box.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &it[i]);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 83