Submission #72009

#	Time	Username	Problem	Language	Result	Execution time	Memory
72009		BOJ 8481 (#118)	Box Run (FXCUP3_box)	C++17	17 / 100	1080 ms	1868 KiB

box

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int h[500010];
int x[2100000];
int base;
int get_max(int s, int e){
	s += base;
	e += base;
	int ret = 0;
	if(s == e) return x[s];
	while(s < e){
		if(s % 2 == 1){
			ret = max(ret, x[s]);
			s += 1;
		}
		if(e % 2 == 0){
			ret = max(ret, x[e]);
			e -= 1;
		}
		s /= 2;
		e /= 2;
		if(s == e){
			ret = max(ret, x[e]);
		}
	}
	return ret;
}
int main(){
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &h[i]);
	}
	base = 1;
	while(base < n) base *= 2;
	for(int i=0; i<n; i++){
		x[base+i] = h[i];
	}
	for(int i=base-1; i>=1; i--){
		x[i] = max(x[2*i], x[2*i+1]);
	}
	for(int width=1; width<=n; width++){
		if(width == n){
			printf("-1\n");
			continue;
		}
		vector<int> temp;
		for(int i=0; i<=n-width; i++){
			temp.push_back(get_max(i, i+width-1));
		}
		bool stuck = false;
		for(int i=1; i<temp.size(); i++){
			if(temp[i] > temp[i-1]){
				stuck = true;
				printf("%d\n", i);
				break;
			}
		}
		if(stuck == false){
			printf("-1\n");
		}
	}
}

Compilation message (stderr)

box.cpp: In function 'int main()':
box.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<temp.size(); i++){
                ~^~~~~~~~~~~~
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:34: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: 0 / 83