Submission #72555

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

box

#include <stdio.h>
int ans[500005], arr[500005];
int it[1100000], loc[1100000];
int maxi, t=1, l;
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];
			l = loc[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, le, ri, k, v;
	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;
		loc[i] = i - t + 1;
		while (p > 0) {
			if (it[p] < it[i]) {
				it[p] = it[i];
				loc[p] = i - t + 1;
			}
			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, le = l;
		for (j = i + 1; j <= n; j = j + i) {
			maxi = 0;
			max_it(j, j + i - 1, 1, t, 1);
			next = maxi, ri = l;
			//printf("%d %d\n", le, ri);
			if (now < next) {
				ans[i]=fd(j, j + i - 1, now)-i;
				break;
			}
			else if (now == next && ri - le > i) {
				for (k = j; k < j + i; k++) {
					maxi = 0;
					max_it(k - i, k - 1, 1, t, 1);
					if (maxi < it[k + t - 1]) {
						ans[i] = k - i+1;
						break;
					}
				}
				if (k < j + 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:19:12: warning: unused variable 'right' [-Wunused-variable]
  int left, right;
            ^~~~~
box.cpp: In function 'int main()':
box.cpp:34:50: warning: unused variable 'v' [-Wunused-variable]
  int n, i, j, p, now, next, flag = 0, le, ri, k, v;
                                                  ^
box.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
box.cpp:41: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