oj.uz

Submission #72164

# Submission time Handle Problem Language Result Execution time Memory
72164 2018-08-26T05:40:19 Z 유애나(#2199, kdh9949) Box Run (FXCUP3_box) C++17
0 / 100
 6 ms 688 KB 
#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){
    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; i++){
        while((2 << j) < i) j++;
        lg[i] = j;
        d[i][0] = i;
    }
    d[n + 1][0] = n + 1;
    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++){
        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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Runtime error 6 ms 688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Runtime error 6 ms 688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -