Submission #72502

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72502	2018-08-26T08:37:31 Z	Semteo For Ajou(#2257, tph00300, txepahs, bmw)	Box Run (FXCUP3_box)	C++17	0 / 100	3 ms	484 KB

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

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.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	3 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Incorrect	2 ms	484 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #2

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	3 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Incorrect	2 ms	484 KB	Output isn't correct
7	Halted	0 ms	0 KB	-