oj.uz

Submission #72009

# Submission time Handle Problem Language Result Execution time Memory
72009 2018-08-26T04:37:28 Z BOJ 8481(#2179, veydpz, jh05013, 16silver) Box Run (FXCUP3_box) C++17
17 / 100
 1000 ms 1868 KB 
#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

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.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 2 ms 484 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 544 KB Output is correct
10 Correct 3 ms 544 KB Output is correct
11 Correct 3 ms 628 KB Output is correct

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 2 ms 484 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 544 KB Output is correct
10 Correct 3 ms 544 KB Output is correct
11 Correct 3 ms 628 KB Output is correct
12 Correct 39 ms 636 KB Output is correct
13 Correct 415 ms 708 KB Output is correct
14 Execution timed out 1080 ms 1868 KB Time limit exceeded
15 Halted 0 ms 0 KB -