Submission #73175

#	Time	Username	Problem	Language	Result	Execution time	Memory
73175		test	Box Run (FXCUP3_box)	C++14	100 / 100	260 ms	36780 KiB

box

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

const int MN = 500010;

int N;
int H[MN];

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4 * N, 0);
    }
    void upd(int idx, int val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = val;
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    int kquer(int k, int l, int r, int n) {
        if(tree[n] < k) return -1;
        if(l == r) return l;
        int m = (l + r)>>1;
        if(tree[2*n + 1] < k) return kquer(k, l, m, 2*n);
        else return kquer(k, m + 1, r, 2*n + 1);
    }
} bit;

int mn[MN];

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d", &H[i]);
    }

    for(int i = 0; i <= N; i++) mn[i] = 1e9;
    bit.init();
    for(int i = 0; i < N; i++) {
        int a = bit.kquer(H[i], 0, N - 1, 1);
        bit.upd(i, H[i], 0, N - 1, 1);
        if(mn[i - a - 1] == 1e9) mn[i - a - 1] = i;
    }
    for(int i = N; i >= 0; i--) {
        mn[i - 1] = min(mn[i - 1], mn[i]);
    }
    for(int i = 1; i <= N; i++) {
        if(mn[i] == 1e9) printf("-1 ");
        else printf("%d ", mn[i] - i + 1);
    }
}

Compilation message (stderr)

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

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