Submission #72168

#	Time	Username	Problem	Language	Result	Execution time	Memory
72168		유애나 (#118)	Box Run (FXCUP3_box)	C++17	100 / 100	482 ms	48600 KiB

box

#include <bits/stdc++.h>
using namespace std;

const int N = 500005;

int n, h[N], lg[N], d[N][20], nx[N];

int g(int s, int e){
    e = min(e, n + 1);
    int l = lg[e - s + 1];
    int x = d[s][l], y = d[e - (1 << l) + 1][l];
    return (h[x] > h[y] || (h[x] == h[y] && x < y)) ? x : y;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", h + i);
    h[n + 1] = int(2e9);
    for(int i = 1, j = 0; i <= n + 1; i++){
        while((2 << j) < i) j++;
        lg[i] = j;
        d[i][0] = i;
    }
    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= n + 1; j++){
            int x = d[j][i - 1], y = d[min(n + 1, j + (1 << (i - 1)))][i - 1];
            if(h[x] > h[y] || (h[x] == h[y] && x < y)) d[j][i] = x;
            else d[j][i] = y;
        }
    }
    for(int i = 1; i <= n; i++){
        nx[i] = i;
        for(int j = 19; j >= 0; j--){
            if(h[d[nx[i]][j]] <= h[i]) nx[i] += (1 << j);
        }
    }
    for(int i = 1; i <= n; i++){
        int t = g(1, i);
        while(t < n){
            int nt = nx[t];
            if(nt <= min(n, t + i)){
                t = nt - i;
                break;
            } 
            else t = g(t + 1, t + i);
        }
        printf("%d ", t >= n ? -1 : t);
    }
    puts("");
    return 0;
}

Compilation message (stderr)

box.cpp: In function 'int main()':
box.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
box.cpp:17:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d", h + i);
                                 ~~~~~^~~~~~~~~~~~~

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