Submission #74343

#	Time	Username	Problem	Language	Result	Execution time	Memory
74343		khsoo01	Box Run (FXCUP3_box)	C++11	100 / 100	155 ms	30720 KiB

box

#include<bits/stdc++.h>
using namespace std;
 
const int N = 500005, L = 524288;
 
int n, a[N];
 
struct segtree {
	int v[2*L];
	void build () {
		for(int i=1;i<=n;i++) {
			v[i+L] = a[i];
		}
		for(int i=L;--i;) {
			v[i] = max(v[2*i], v[2*i+1]);
		}
	}
	int lb (int I, int V) {
		I += L;
		while(I&(I+1)) {
			if(v[I] >= V) break;
			I = (I-1)/2;
		}
		if((I&(I+1)) == 0) return 0;
		while(I < L) {
			I = 2*I + (v[2*I+1] >= V);
		}
		return I - L;
	}
} seg;
 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	seg.build();
	int I = 1;
	for(int i=1;i<=n;i++) {
		int T = i - seg.lb(i-1, a[i]) - 1;
		while(I <= T) {
			printf("%d ",i-I);
			I++;
		}
	}
	for(int i=I;i<=n;i++) {
		printf("-1 ");
	}
}

Compilation message (stderr)

box.cpp: In function 'int main()':
box.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
box.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 83 / 83