oj.uz

답안 #72127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72127 2018-08-26T05:25:55 Z 유애나(#2199, kdh9949) 박스런 (FXCUP3_box) C++17
0 / 100
 2 ms 356 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;

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

int g(int s, int e){
    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);
    for(int i = 1, j = 0; i <= n; 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; 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++){
        int t = g(1, i);
        while(t < n){
            int nt = g(t + 1, t + i);
            if(h[t] < h[nt]){
                t = nt - i;
                break;
            }
            else t = nt;
        }
        printf("%d ", t >= n ? -1 : t);
    }
}

Compilation message

box.cpp: In function 'int main()':
box.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
box.cpp:16: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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 KB Output is correct
2 Incorrect 2 ms 356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 KB Output is correct
2 Incorrect 2 ms 356 KB Output isn't correct
3 Halted 0 ms 0 KB -