답안 #72555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72555	2018-08-26T08:59:37 Z	Semteo For Ajou(#2257, tph00300, txepahs, bmw)	박스런 (FXCUP3_box)	C++17	0 / 100	3 ms	536 KB

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

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.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	536 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	3 ms	536 KB	Output is correct
6	Incorrect	2 ms	536 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #2

0 / 83.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	536 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	3 ms	536 KB	Output is correct
6	Incorrect	2 ms	536 KB	Output isn't correct
7	Halted	0 ms	0 KB	-