Submission #72187

#	Time	Username	Problem	Language	Result	Execution time	Memory
72187		우리는 진실을 잊고 살잖아~~~ (#118)	Box Run (FXCUP3_box)	C++11	100 / 100	405 ms	9516 KiB

box

#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_N 500000

int N;
int H[MAX_N];
int tree[MAX_N*4];
int ans[MAX_N];

int init(int left, int right, int node)
{
    if(left == right) return tree[node] = H[left];
    int mid = (left + right)/2;
    return tree[node] = max(init(left, mid, node*2), init(mid+1, right, node*2+1));
}

int max_range(int left, int right, int node, int start, int end)
{
    if(start <= left && right <= end) return tree[node];
    if(right < start || left > end) return 0;
    int mid = (left+right)/2;
    return max(max_range(left, mid, node*2, start, end), \
               max_range(mid+1, right, node*2+1, start, end));
}

int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d", &N);
    for(int i=0;i<N;++i) scanf("%d", &H[i]);
    init(0, N-1, 1);

    int w = 1, p = 0;
    while(w<=N && p<N){
        if(p-w>=0 && max_range(0, N-1, 1, p-w, p-1) < H[p]){
            printf("%d ", p-w+1);
            w++;
        }else p++;
    }
    while(w++<=N) printf("%d ", -1);
    return 0;
}

Compilation message (stderr)

box.cpp: In function 'int main()':
box.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
box.cpp:31:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<N;++i) scanf("%d", &H[i]);
                          ~~~~~^~~~~~~~~~~~~

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